Maximum sum in contiguous subarray

This is very famous interview question.
Given an array A of integers (both positive and negative) and you need to find the maximum sum found in any contiguous subarray of A.

Example A = [11, -12, 15, -3, 8, -9, 1, 8, 10, -2]
Answer is 30.

There are many solutions to this problem.

Method 1 Brute Force

int maxSum(int a[],int n)
{
  int i,j,k;
  int sum,maxSum = 0;
  for(i=0; i<n; i++)
  {
    for(j=i; j<n; j++)
    {
      sum = 0;
      for(k=i ; k<j; k++)
      {
        sum = sum + a[k];
      }
      if(sum>maxSum)
        maxSum = sum;
    }
   }
   return maxSum;
}

Time Complexity O(n^3)

Method 2 Quadratic

int maxSum(int a[],int n )
{
    int i,j,sum,maxSum;
    maxSum = 0;
    for(i = 0;i<n;i++)
    {
        sum = 0;
        for(j=i;j<n;j++)
        {
            sum = sum + a[j];
            if(sum>maxSum)
                maxSum = sum; 
        }
    }
    return maxSum;
}

Time Complexity O(n^2)

Method 3

Kadane’s Algorithm:
The idea is to keep scanning through the array and calculating the maximum sub-array that ends at every position. The sub-array will either contain a range of numbers if the array has intermixed positive and negative values, or it will contain the least negative value if the array has only negative values.

int maxSum(int a[], int n)
{
   int maxSum = 0,sum = 0;
   int i;
   for(i = 0;i<n;i++)
   {
     sum = sum + a[i];
     if(sum < 0)
        sum = 0;
     else if(sum > maxSum)
        maxSum = sum;
   }
   return maxSum;
}

Time Complexity : O(n)

10 Thoughts on “Maximum sum in contiguous subarray

  1. Vishal on July 8, 2013 at 11:58 pm said:

    Is there any way from method 3 so we can get the sub array that has max sum?

  2. crazyadmin on July 9, 2013 at 11:14 pm said:

    Yes Vishal , We can get the sub array with max sum.Below is the code for that ,where
    start_index is the starting index of sub array and end_index is the ending index of sub array.

    int start_index,end_index,start_index_so_far = 0;
    int maxSum(int a[], int n)
    {
       int maxSum = 0,sum = 0;
       int i;
       for(i = 0;i<n;i++)
       {
         sum = sum + a[i];
         if(sum < 0)
         {
            sum = 0;
            start_index_so_far = i+1;
         }
         else if(sum > maxSum)
         {
            maxSum = sum;
            start_index = start_index_so_far;
            end_index = i;
         }
       }
       return maxSum;
    }
    
  3. Great information. Lucky me I found your site by chance (stumbleupon).

    I’ve book-marked it for later!

  4. Dynamic Programing:
    getMax(int[] arr, int start,int end)
    {
    if(start > end)
    return 0;
    return max(arr[start] + getMax(arr,start + 1,end), getMax(arr,start + 1,end));
    }

  5. Shobhank on December 7, 2014 at 12:23 pm said:

    public static void maxSumSubsequence(int a[]){
    int meh = 0,msf = 0,s=-1,e=-1;
    for(int i=0;i<a.length;i++){
    if(meh+a[i]<0){
    meh = 0;
    s = i+1;
    }else{
    meh = meh + a[i];
    }
    if(msf<meh){
    msf = meh;
    e = i;
    }
    }
    System.out.println("Max Sum Subsequence " + msf);
    System.out.println("Start:" + s + " End:" + e);
    }

  6. For method 2, the input 1, -1 ,-1, -1, -1, 5 will give the wrong output. It outputs 2 where the actual output should have been 5.
    for (int i = 0; i < Array.Length; i++)
    {
    int localSum = 0;
    for (int j = 0; j < Array.Length; j++)
    {
    localSum = localSum + Array[j];
    if (localSum 0) { localSum = 0; }
    if (Sum < localSum) { Sum = localSum; }
    }
    }

    The extra condition, if (localSum 0) { localSum = 0; }, should solve it.

  7. codebarer on April 27, 2015 at 10:10 am said:

    Logic for method one is incorrect.

    Tried several arrays below and they gave wrongs sub array values:
    [1, 2, 4, -1, 4, -10, 4, -19, 18, -1, -3, -4, 11, 3, -20, 19, -33, 50, 66, -22, -4, -55, 91, 100, -102, 9, 10, 19, -10, 10, 11, 11, -10, -18, 50, 90]

    [12, 12, 14, -88, -1, 45, 6, 8, -33, 2, 8, -9, -33, -8, -23, -77, -89, 1, 9, 10, 92, 87]

    [2, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3]

  8. its does’nt work when all value are nagative than gretest nagative value is replace by 0

Leave a Reply

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

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=""> <strike> <strong>

Post Navigation