Greatest Sum of Sub-Arrays…


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)

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s