Here is a slightly more complicated one:

Q. Given an integer array containing N positive and negative numbers, find the sub-array having the largest sum in linear time O(N) using constant space O(1).

Want some hint?

You need to keep track of both the maximum sum so far and the maximum sum for including an element.

My solution (in Java):

int[] largestSum(int... a) {
int start = 0, end = -1, curstart = 0, last = 0, sum = Integer.MIN_VALUE;
for (int i = 0;i < a.length; i++) {
last += a[i];
sum = Math.max(last, sum);
if (sum == last) {
start = curstart;
end = i;
}
if (last < 0) {
last = 0;
curstart = i + 1;
}
}
return Arrays.copyOfRange(a, start, end + 1);
}

### Like this:

Like Loading...

*Related*

Sorry, but your code gives incorrect results. Just test it with an input array of

[-80, 4, 6, -80, 4, 7, -80]. It is obvious that [4, 7] is the correct result (sum = 11), but your code returns [4, 6, -80, 4, 7] (sum = -59).

Thanks for catching the bug. I’ve fixed the solution.