Given an array of positive and negative values. We have to find the maximum sum a sub-array can have.
For example the the array {-1, 7, -2, 4, -3, -9, 2} has a maximum sum of 9 which corresponds to the sub-array {7, -2, 4}.
To solve this problem, we take two variables to keep track of running sum and maximum sum. While iterating through the array, we keep adding the elements to the running sum. If the running sum exceeds the maximum sum, we update the maximum sum to reflect the latest maximum. If it becomes negative we reset it to zero. At the end of the iteration maximum sum variable contains the required value.
If all the elements are negative, then this program gives an output of 0 (basically the sum of zero-length sub-array). This program runs in O(n) time and O(1) space.
/**
* Created with IntelliJ IDEA.
* User: Ravi
* Date: 9/25/13
* Time: 10:45 PM
* To change this template use File | Settings | File Templates.
*/
public class Main {
public static void main(String[] args)
{
int[] array = {-1, 4, -2, 3, 0, -5, 1, 2};
System.out.println("Maximum sum of sub-array is " + getMaxSum(array));
int[] array1 = {-2, -3, 4, -1, -2, 1, 5, -3};
System.out.println("Maximum sum of sub-array is " + getMaxSum(array1));
}
public static int getMaxSum(int[] array)
{
int maxSum = 0;// to keep track of maximum sum
int curSum = 0;// running sum
int i;
for( i = 0; i < array.length; i++ )
{
curSum += array[i];
if( curSum < 0 ) //reset if sum becomes negative
{
curSum = 0;
}
if( maxSum < curSum ) // update maxSum
maxSum = curSum;
}
return maxSum;
}
}