Largest Sum Contigous SubArray in C++

May 2, 2023

Largest Sum Contigous Subarray in C++

Largest Sum Contiguous Subarray in C++

Here, in this page we will discuss the program to find the largest sum contiguous subarray in C++. We will discuss two different ways in this page for finding such subarray.

Largest Sum Contiguous Sub-Array in C++

The problem of finding the largest sum contiguous subarray in a given array involves identifying a subarray within the array that has the highest sum of its elements. This means we are searching for a continuous subarray in the given array that has the maximum possible sum.

For example, consider the following array:

arr = [-2, -3, 4, -1, -2, 1, 5, -3]

The largest sum contiguous subarray in this array is [4, -1, -2, 1, 5], which has a sum of 7.

The problem of finding the largest sum contiguous subarray has a well-known algorithm called Kadane’s algorithm. The algorithm has a time complexity of O(n) and can be easily implemented in C++.

 
Largest Sum Contiguous Sub-Array in C++

Method Discussed :

  • Method 1 : Brute Force Approach.
  • Method 2 : Using Kadane’s Algorithm

Method 1 :

  • Declare a variable say res = INT_MIN.
  • Run a loop from index 0 to n.
  • Declare a variable sum = 0;
  • Run a nested loop from index i to n.
  • Set sum += arr[j].
  • And res = max(res, sum)
  • After Complete Iteration print res.

Time and Space Complexity :

  • Time Complexity : O(n2)
  • Space Complexity : O(1)
DSA desktop gif
DSA mobile gif

Given an array which consists of only 0, 1
Move all the negative elements to one side of the array

Minimum no. of Jumps to reach the end of an array 

Find Largest sum contiguous Subarray

Minimize the maximum difference between heights 

Method 1 : Code in C++

Run 
#include <bits/stdc++.h>
using namespace std;
 
int main()
{
    int arr[] = {-2, -3, 4, -1, -2, 1, 5, -3};
    int n = sizeof(arr)/sizeof(arr[0]);
    
    int res = INT_MIN;
    
    for(int i=0; i<n; i++){
        int sum = 0;
        for(int j=i; j<n; j++){
            sum += arr[j];
            res = max(sum, res);    
        }
    }
    
    cout<<res;
}

Output

7

Method 2 :

  • Create variable say max_sum that hold the required maximum sum of subarray and curr_sum and initialize max_sum with INT_MIN and curr_sum with 0.
  • Now, iterate over the array, and for every ith value of the array, add it to curr_sum, and comapre it with max_sum like,
  • if(max_sum < curr_sum) max_sum = curr_sum.
  • Now, check if curr_sum <0 then set curr_sum to 0.
  • After complete iteration we will get the result that store in max_sum variable.

Time and Space Complexity :

  • Time Complexity : O(n)
  • Space Complexity : O(1)

Method 2 : Code in C++

Run 
#include <bits/stdc++.h>
using namespace std;
 
int main()
{
    int arr[] = {-2, -3, 4, -1, -2, 1, 5, -3};
    int n = sizeof(arr)/sizeof(arr[0]);
    
    int max_sum = INT_MIN, curr_sum =0;

    for(int i=0; i< n; i++){
    
       curr_sum += arr[i];
    
       if(max_sum < curr_sum)
            max_sum = curr_sum;
    
       if(curr_sum < 0)
            curr_sum = 0;
    
    }
    
    cout << max_sum;
}

Output

7

Prime Course Trailer

Related Banners

Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription

Get Prime

Get over 200+ course One Subscription

Courses like AI/ML, Cloud Computing, Ethical Hacking, C, C++, Java, Python, DSA (All Languages), Competitive Coding (All Languages), TCS, Infosys, Wipro, Amazon, DBMS, SQL and others

Get Prime
Course List
Course List

Checkout list of all the video courses in PrepInsta Prime Subscription

Checkout list of all the video courses in PrepInsta Prime Subscription

Checkout
Checkout

Arrays

  • Introduction to Arrays – C | C++ | Java
  • Introduction to 2-D Arrays – C | C++ | Java
  • Sorting of Array – C | C++ | Java
  • Array Rotation – C | C++ | Java
  • Reverse an array or string- C | C++ | Java
  • Find pairs in array with given sum – C | C++ | Java
  • Sort the array in Waveform – C | C++ | Java
  • Majority Element in Array – C | C++ | Java
  • Boyer-Moore’s Voting Algorithm – C | C++ | Java
  • K-pairs with smallest sum in 2 arrays – C | C++ | Java
  • Largest Sum Contigous SubArray – C | C++ | Java
  • Maximum Average Sub-array of K length – C | C++ | Java
  • Size of sub-array with max sum – C | C++ | Java
  • Sub-array with given sum – C | C++ | Java
  • Triplet that sum to a given value – C | C++ | Java
  • Segregate 0’s and 1’s in array – C | C++ | Java
  • Segregate 0’s 1’s and 2’s in array – C | C++ | Java
  • Sort elements in array by frequency – C | C++ | Java
  • Finding pythagorean triplets in an array – C | C++ | Java
  • Reorder array using given indexes – C | C++ | Java
  • Merging two sorted arrays – C | C++ | Java
  • Minimum number of Merge Operations to make an Array Palindrome – C | C++ | Java
  • Find Zeros to be Flipped so that number of Consecutive 1’s is maximized – C | C++ | Java