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)
Is there any way from method 3 so we can get the sub array that has max sum?
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.
Great information. Lucky me I found your site by chance (stumbleupon).
I’ve book-marked it for later!
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));
}
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);
}
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.
Sorry, typing error. if (localSum 0) { localSum = 0; }, is the condition
Sorry, my mistake. Your code works just fine. I had set the starting value for j in the second loop incorrectly.
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]
its does’nt work when all value are nagative than gretest nagative value is replace by 0
I believe an extra for loop should solve problem when all elements are negative
#include
int minSum(int a[], int n);
int main()
{
int arr[] = {1,-1,-2,3};
int p = minSum(arr,4);
printf(“%d”,p);
return 0;
}
int minSum(int a[], int n)
{
int minSum = 999,sum = 0;
int i;
// if all are positive elements in array
for(i=0;i=0)
{
if(a[i] < minSum)
minSum = a[i];
}
else
break;
}
//if there are mixed elements
if(i==n)
return minSum;
else
{
for(i=0;i 0)
sum = 0;
else if(sum < minSum)
minSum = sum;
}
}
return minSum;
}
sorry i was working on minsum, but the logic is similar