Maximum sum contiguous subarray of an Array

Given an Array A with n integers both positive and negative, find the maximum sum contiguous subarray within A which has the largest sum

Naive Approach –

You can find the sum of all subarrays present in the array and determine the maximum among them. This approach will run in O(n²) time complexity.

Below is the implementation of above idea in C++ :

#include<bits/stdc++.h>
using namespace std;

int main()
{
    int n;
    cin>>n;

    int A[n];
    for(int i=0;i<n;i++) 
    cin>>A[i];
 
    long long max_ans;
    max_ans=A[0];

    for(int i=0;i<n;i++)
    {
        long long result=0;
        for(int j=i;j<n;j++)
        {
            result+=A[j];
            max_ans=max(max_ans,result);
        }
    }
 
    cout<<max_ans;
    return 0;
}

 

Efficient Method to find Maximum Sum Contiguous subarray:

Kadane’s algorithm finds the maximum sum subarray in O(n) time complexity which involves finding the maximum sum subarray possible ending at each indexes. This algorithm is a very simple application of dynamic programming i.e. it uses the previously calculated values to find the next value which is to be calculated. Basically this algorithm calculates two values the maximum sum until the current index and the maximum sum so far. Each time we iterate we compare and update these two variables. We get the maximum sum subarray after we traverse the array once.

Initially store A[0] in curr_max and overall_max variables since it is the maximum we can have when we have only the first element. For index 1 we find the maximum between A[1] and (curr_max + A[1]). Thus if the element at index 1 is greater than the sum of subarray [0,1] it will be updated as the curr_max or else the subarray [0,1] will be the current maximum sum ending at that index. In the next iteration we will again find the maximum between the current element and the maximum sum subarray that we had calculated before, so it is guaranteed that we will have the maximum subarray sum with us if we had i elements. While doing so we also update the variable overall_max, which essentially just finds out the maximum of all the curr_max values of all i. Thus after traversing the whole array we have the maximum sum of a contiguous subarray stored in overall_max.

Algorithm:

Initialize variables:
overall_max=A[0];
curr_max=A[0];

Iterate over the Array A:
{
  Update curr_max with the maximum of (A[i]) and (curr_max + A[i]);
  Update overall_max with the maximum of (curr_max) and (overall_max);
}

 

Below is the implementation of the above algorithm in C++:

#include<bits/stdc++.h>
using namespace std;
 
long long KadaneMaxSumSubarray(long long A[],int size)
{
    long long overall_max = A[0];
    long long curr_max = A[0];
 
    for (int i=1;i<size;i++) 
    { 
        curr_max = max(A[i],curr_max + A[i]);
        overall_max = max(overall_max, curr_max);
    } 
    return overall_max;
} 

int main()
{ 
    int n;
    cin>>n;
 
    long long A[n];
    for(int i=0;i<n;i++)
    cin>>A[i];
 
    long long max_sum=KadaneMaxSumSubarray(A,n);
    cout<<max_sum;
    return 0;
}