Kadane's Algorithm to find maximum subarray sum

Given an array of n integers (both +ve and -ve). Find the contiguous sub-array whose sum is maximum (More than 1 sub-array may have same sum). For Example:

      Array               Maximum Sub-Array         sum
-----------------------  -----------------------   ----
{5, 7, 12, 0, -8, 6}        {5, 7, 12}              24
{6, -2, -3, 4, -1, 10 }  {6, -2, -3, 4, -1, 10 }    14
{-1, -3, 4, -7, 0, 2}       {2}                     2
{1, -5, 2, -1, 3}           {2, -1, 3}              4

Note: If all elements are positive, then the result is sum of entire array. If all elements are -ve then result is zero.
1. Brute-Force Method – O(n³) Time

This method is to find all the possible sub-array of the array. Compute the Sum of all the sub-arry and then find the maximum out of them.

If there are n elements, then total number of sub-array possible are

n + (n-1) + (n-2) + .... + 1 = O(n^2)

Computing sum of elements of a sub-array will take O(n) time. Hence the total time is O(n³).

( Finding max of O(n²) elements will take O(n²) time.)

Code:

    /**
     * Function will compute the maximum subarray.
     *
     * Will set the variables 'start' and 'end' to proper indeces
     * of the maximum subarray.
     */
    void maxSubArray( int* arr, int n, int* start, int* end)
    {
        int sum, max = arr[0];
        for (int i = 0; i < n ; i++)
            for (int j = i; j < n; j++)
            {
                sum = 0;
                for (int k = i; k <=j; k++)
                    sum+= arr[k];
                if (sum >= max)
                {
                    *start = i;
                    *end = j;
                }
            }
    }

2. Improvement over Method-1 – O(n²) Time

The above algorithm can be slightly improved to take O(n²) time by changing the way we are computing sum of sub-arrays. Let arr[i .. j] represents – “sum of sub-array from position i to j“, then this algorithm uses the fact that

arr[i .. j] = arr[j] + arr[i .. j-1]

Hence, we will not compute the sum of entire sub-array every time, but reuse the sum of previously computed sub-array to get the sum of current sub-array.

/**
 * Improvement over the function in point-1
 *
 * Sum of subarray arr[i .. j] = arr[j] + sum of subarray arr[i .. j-1]
 */
void maxSubArray(int *arr, int n, int &start, int &end)
{
    int sum, max = arr[0];
    for (int i = 0; i < n; i++)
    {
        sum = 0;
        for (int j = i; j < n; j++)
        {
            sum + = arr[j];
            if (sum >= max)
            {
                start = i;
                end = j;
            }
        }
    }
}

3. Kadane’s Algorithm (Using Dynamic Programming) – O(n) Time

This problem can be solved in linear time using Dynamic Programming. There are O(n) subproblems, each of which can be solved using the previously solved subproblem.

It uses two variables as shown in the algorithm at this wiki page

Algorithm:

// Two variables to store results
max_ending_here = max_so_far = 0
for i = 0 to n-1
    max_ending_here = max(a[i], max_ending_here + a[i])
    max_so_far = max(max_so_far, max_ending_here)
return max_so_far

Code:

    int maxSubArraySum(int *arr, int n)
    {
        int max_so_far = 0;
        int max_ending_here = 0;
        for(int i = 0; i < n; i++)
        {
            max_ending_here = max_ending_here + arr[i];
            if(max_ending_here < 0)
                max_ending_here = 0;
            if(max_so_far < max_ending_here)
                max_so_far = max_ending_here;
        }
        return max_so_far;
    }

References:

http://www.cs.cmu.edu/~15210/lectures/lecture03.pdf
http://en.wikipedia.org/wiki/Kadane%27s_Algorithm