Maximum continuous sum problem

You are given an array of integers (both positive and negative). Find the continuous sequence with the largest sum. Return the sum.
EXAMPLE
Input: {2, -8, 3, -2, 4, -10}
Output: 5 (i.e., {3, -2, 4})

My initial thoughts:
We need to track two variables: max sum ending at position i and max sum so far. We update maxSumEndHere to zero if adding the current element will make the sum be negative, otherwise we keep track of the maximum sum. We update maxSumSoFar according to maxSumEndHere. We then return maxSumSoFar.
My initial code:

	public static int maxContinousSum(int[] array) {
		int maxSumEndHere = 0;
		int maxSumSoFar = Integer.MIN_VALUE;
		for (int number : array) {
			if (maxSumEndHere + number > 0)
				maxSumEndHere = maxSumEndHere + number;
			else
				maxSumEndHere = 0;
			if (maxSumEndHere > maxSumSoFar)
				maxSumSoFar = maxSumEndHere;
		}
		return maxSumSoFar;
	}

Solution:

	public static int getMaxSum(int[] a) {
		int maxsum = 0;
		int sum = 0;
		for (int i = 0; i < a.length; ++i) {
			sum += a[i];
			if (maxsum < sum) {
				maxsum = sum;
			} else if (sum < 0) {
				sum = 0;
			}
		}
		return maxsum;
	}

The cleanest one:

	public static int maxContinousSum2(int[] A) {
		int maxSoFar = 0;
		int maxEndingHere = 0;
		for (int x : A) {
			maxEndingHere = Math.max(x, maxEndingHere + x);
			maxSoFar = Math.max(maxSoFar, maxEndingHere);
		}
		return maxSoFar;
	}

Comments:
All of the above methods assume that if we have an array of all negative numbers, we return sum of zero.

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

%d bloggers like this: