Given a list of integers with positive and negative numbers, we want to find sum of maximum sub array with greatest sum. This means the numbers we added together has to be next to each other.
Example 1:
Given a = { 1,-1,2,4,1,-8,10,9} Ans: 19 since the sub array {10,9} gives the largest sum
Example 2:
{ 3, -8, 9, 7, -6 , 0, 1} Ans 9 + 7 = 16
Example 3:
{ 2, -8, 3, -2, 4, -10 }) Ans: 5
Example 4:
{ 2, -8, 3, 4, 7, -20, 4, -10,1 } Ans: 14
Example 5
{ -2, 1, -3, 4, -1, 2, 1, -5, 4 } Ans: 6
Solution
There are two optimal solutions for this question.
Method 1:
We need two variables to track the temp max and the actual max or sum we need to find.
The temp max (lets call it sum) always tries to compare what is in it (sum) with what is in front of it plus sum.
This means we will try to calculate the sum of the adjacent array elements and try to take the max of its current array element or sum plus the current array element.
In other words , sum= Math.Max(a(i), sum+ a(i))
This will be a good solution if there are no negative numbers. As soon as we encounter them our sum goes down significantly. Therefore, we need to store the sum value to another actual maxsum variable before we reset it (reduce the value) when we see the negative number.
int sum= A[0];
int maxsum= A[0];
for (int i = 1; i < A.Length; i++) {
sum= Math.Max(A[i], A[i] + sum);
maxsum= Math.Max(sum, maxsum);
}
return maxsum;
Here we ask the question do we get the greater sum by considering the cumulative sum or it is better off Just taking the number at this index. (Like a business owner reevaluating the contribution of all the sum of the workers and deciding if it will be a good idea taking in that as part of the total effort. If it is not worth equal or greater than the boss effort by himself then don’t even bother including them in the process.)
Let us trace the last example:
Iteration 1: sum: 1, MaxSoFar: 1
Iteration 2: sum: -2, MaxSoFar: 1
Iteration 3: sum: 4, MaxSoFar: 4
Iteration 4: sum: 3, MaxSoFar: 4
Iteration 5: sum: 5, MaxSoFar: 5
Iteration 6: sum: 6, MaxSoFar: 6
Iteration 7: sum: 1, MaxSoFar: 6
Iteration 8: sum: 5, MaxSoFar: 6
The sum of the contiguous subarray with the largest sum is: 6
The running time of this algorithm is liner time O(N).
Method 2:
The second approach is to keep adding each elements for the array until the sum goes below 0 and it does we reset the sum to 0 and if not we keep updating our maxsum when we get a new bigger sum. We reset sum to zero if it goes below 0 because if all the numbers before a certain number add up to 0 or less then we can ignore the whole sub array and assume we start a new array with the remaining items. We also tend to think the same way when we think about how to solve this kind of problem.
int Maxsum = 0;
int sum = 0;
for (int i = 0; i < A.Length; i++) {
sum += A[i];
if (sum < 0)
sum = 0;
else if(sum > Maxsum) {
Maxsum = sum;
}
}
return Maxsum;