Aug 192012
 

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(n3) Time

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

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

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

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

( Finding max of O(n2) elements will take O(n2) 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(n2) Time

The above algorithm can be slightly improved to take O(n2) 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 sequence arr[i .. j] = arr[j] + sum of sequence 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

  3 Responses to “Kadane’s Algorithm to find maximum subarray sum”

Comments (3)
  1. wrong Kadane’s Algorithm
    Doesnt work for [-1,-2]

  2. Isnt in the 3rd example sub array would be {4}

  3. Hello there, just became aware of your weblog by way of Google, and identified that it is actually informative. I’m going to watch out for brussels. I’ll be grateful in the event you continue this in future. Lots of people will probably be benefited from your writing. Cheers!

 Leave a Reply

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

(required)

(required)