check if all nodes of a tree has only one child
August 18, 2012
Number of nodes in a binary tree
August 22, 2012

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

7 Comments

  1. testdomain says:

    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!

  2. vaibhav says:

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

  3. Rajat Singla says:

    wrong Kadane’s Algorithm
    Doesnt work for [-1,-2]

  4. stevedillard says:

    I am glad I was able to discover this informative article. Of course, I cannot say that it is easy to follow, but I am certain that http://puressay.com/blog/top-10-books-that-are-able-to-transform-your-life will be something new for you to peruse.

  5. click here says:

    Thank you so much for sharing such a superb information’s with us. Your website is very cool. we are impressed by the details that you have on your site.we Bookmarked this website. keep it up and again thanks

  6. prajwal says:

    please give me the logic to print that subarray also

Leave a Reply to Anonymous Cancel reply

Your email address will not be published. Required fields are marked *