Maximum sum sub-array

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);
    }
Advertisements