## 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;
}

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

__ATA.cmd.push(function() {
__ATA.initVideoSlot('atatags-370373-5c9102949fa24', {
sectionId: '370373',
});
});

__ATA.cmd.push(function() {
__ATA.initSlot('atatags-26942-5c9102949fa60',  {
collapseEmpty: 'before',
sectionId: '26942',
width: 300,
height: 250
});
});

__ATA.cmd.push(function() {
__ATA.initSlot('atatags-114160-5c9102949fa63',  {
collapseEmpty: 'before',
sectionId: '114160',
width: 300,
height: 250
});
});