Maximum subarray problem (Kadane’s algorithm)

Problem: Given an array of integers, find subarray which has the largest sum.

For example:

Input: arr[] = {-2, -3, 4, -1, -2, 1, 5, -3}
Output: 7

The subarray with maximum sum is {4, -1, -2, 1, 5}

Input: arr[] = {-2, 1, -3, 4, -1, 2, 1, -5, 4}
Output: 6

The subarray with maximum sum is {4, -1, 2, 1}

We can easily solve this problem using Kadane's Algorithm. Simple idea of the Kadane's algorithm is to look for all positive contiguous segments of the array (max_ending_here). And keep track of maximum sum contiguous segment among all positive segments (max_so_far). Each time we get a positive sum compare it with max_so_far and update max_so_far if it is greater than max_so_far.

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

/* function to return maximum sum subarray */
int MaxSumSubArray(int arr[], int n)
{
    /* maximum sum sub-array found so far */
    int max_so_far = 0;
 
    /* maximum sum of sub-array ending at current position */
    int max_ending_here = 0;
 
    for (int i = 0; i < n; i++)
    {
        /* update maximum sum of sub-array ending at 
           index i */
        max_ending_here = max_ending_here + arr[i];
 
        /* if maximum sum is negative, set it to 0 
           (empty sub-array) */
        max_ending_here = max(max_ending_here, 0);
 
        /* update result if current sub-array sum is 
           found to be greater*/
        max_so_far = max(max_so_far, max_ending_here);
    }
 
    /* return result */
    return max_so_far;
}

/*driver function */
int main()
{
    int arr[]={-2, -3, 4, -1, -2, 1, 5, -3};
    int len = sizeof(arr)/sizeof(arr[0]);
    
    cout<<MaxSumSubArray(arr, len)<<"\n";
}

Output:

7

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

Above code doesn’t handle the case when all elements of the array are negative. If the array contains all negative values, the answer is the maximum element. We can easily place this check before continuing to the algorithm.

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

/* function to return maximum sum subarray */
int MaxSumSubArray(int arr[], int n)
{
    int max_curr = arr[0];
    int max_so_far = arr[0];
    for(int i=1; i<n; i++)
    {
        max_curr = max(arr[i], max_curr + arr[i]);
        max_so_far = max(max_curr, max_so_far);
    }
    return max_so_far;   
}

/*driver function */
int main()
{
    int arr[]={-2, -3, -4, -1, -2, -1, -5, -3};
    int len = sizeof(arr)/sizeof(arr[0]);
    
    cout<<MaxSumSubArray(arr, len)<<"\n";
}

Output:

-1

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

References:
http://en.wikipedia.org/wiki/Kadane%27s_Algorithm
https://en.wikipedia.org/wiki/Maximum_subarray_problem