Question : Given an integer array containing positive and negative numbers, how do you get the maximum

sum of its sub-arrays? Continuous numbers form a sub-array of an array.For example, if the input array is {1, -2, 3, 10, -4, 7, 2, -5}, the sub-array with the maximum sum is {3, 10, -4, 7,2} whose sum 18.

Let’s accumulate each number in the sample array from beginning to end. Our solution initializes sum

as 0. In the first step, it adds the first number 1, and sum becomes 1. And then if it adds the second

number -2, sum becomes -1. At the third step, it adds the third number 3. Notice that the previous sum is

less than 0, so the new sum will be 2 and it is less than the third number 3 itself. Therefore, the previous

accumulated sum -1 should be discarded.

The key point here is that when the sum becomes a negative number or zero, adding this sum to the

following array element will not be greater than the element itself, so the new sub-array will start from

the next element.

It continues accumulating from the next number with sum 3. When it adds the fourth number 10,

sum becomes 13, and it decreases to 9 when it adds the fifth number -4. Notice that the sum with -4 is

less than the previous sum 13 because of the negative number -4. It saves the previous sum 13 since it

might be the max sum of sub-arrays.

At the sixth step, it adds the sixth number 7 and sum becomes 16. Now sum is greater than the

previous max sum of sub-arrays, so the max sum is updated to 16. It is similar when it adds the seventh

number 2. The max sum of sub-arrays is updated to 18. Lastly it adds -5 and sum becomes 13. Since it is

less than the previous max sum of sub-arrays, the final max sum of sub-arrays remains 18, and the subarray

is {3, 10, -4, 7, 2} accordingly.

int getGreatestSumOfSubArray(int[] numbers) {
int curSum = 0;
int greatestSum = Integer.MIN_VALUE;
for(int i = 0; i < numbers.length; ++i) {
if(curSum <= 0)
curSum = numbers[i];
else
curSum += numbers[i];
if(curSum > greatestSum)
greatestSum = curSum;
}
return greatestSum;
}

(Apress.Coding.Interviews.Questions.Analysis.and.Solutions)

### Like this:

Like Loading...

*Related*