# Ambiguity for negative numbers.

• This is a well-known problem, for example, Jon Bentley has quite a good treatment in his book `Programming Perls'. But the answer, as well as the solution details, depends on what the 'maximum sum' is defined for negative numbers.

For example [-1, -3, -2]. A natural approach is to consider the sum of empty array as zero, sum([]) = 0. Because empty array [] is sub array of all arrays.

The concise solution based on this assumption is as the following:

``````int maxsum(int* xs, int n) {
int i, m, sum;
for (i = m = sum = 0; i < n; ++i) {
sum = max(sum + xs[i], 0);
m = max(m, sum);
}
return m;
}
``````

Where max can be defined either as macro or function like:

``````int max(int a, int b) { return a < b ? b : a; }
``````

However, the OJ system does NOT treat empty array as valid sub-array. It forces the sub-array contains at least one element, Thus we need adjust the above solution a bit:

``````int ojpass(int* xs, int n) {
int i, m, sum;
for (m = sum = xs[0], i = 1; i < n; ++i) {
sum = max(sum + xs[i], xs[i]);
m = max(m, sum);
}
return m;
}``````

• Just for fun: 1 line Python solver:

``````return reduce(lambda m, n: [max(m[0], max(m[1]+n, n)), max(m[1]+n, n)], nums[1:], [nums[0], nums[0]])[0]
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.