Max Non Negative Sub Array

Find out the maximum sub-array of non negative numbers from an array.
The sub-array should be continuous. That is, a sub-array created by choosing the second and fourth element and skipping the third element is invalid.

Maximum sub-array is defined in terms of the sum of the elements in the sub-array. Sub-array A is greater than sub-array B if sum(A) > sum(B).

A : [1, 2, 5, -7, 2, 3]
The two sub-arrays are [1, 2, 5] [2, 3].
The answer is [1, 2, 5] as its sum is larger than [2, 3]

NOTE: If there is a tie, then compare with segment's length and return segment which has maximum length
NOTE 2: If there is still a tie, then return the segment with minimum starting index

思路:

这题比较直接，就照着题目要求scan array一遍就可以了。

Solution:

Time: O(n)
Space: O(n)

public class Solution {
    public ArrayList<Integer> maxset(ArrayList<Integer> A) {
        ArrayList<Integer> result = new ArrayList<>();
        ArrayList<Integer> curr = new ArrayList<>();
        long max = 0;
        long currSum = 0;
        for (int i = 0; i < A.size(); i ++) {
            int n = A.get(i);
            if (n < 0) {
                if (currSum > max) {
                    max = currSum;
                    result = curr;
                } else if (currSum == max && curr.size() > result.size()) {
                    result = curr;
                }
                curr = new ArrayList<>();
                currSum = 0;
            } else {
                curr.add(n);
                currSum += n;
            }
        }
        if (currSum > max) {
            max = currSum;
            result = curr;
        } else if (currSum == max && curr.size() > result.size()) {
            result = curr;
        }
        return result;
    }
}