# 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]

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)

```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

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