Max Non Negative SubArray

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).

Example:

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

Solution: Update using sliding window technique

vector<int> Solution::maxset(vector<int> &A) {
    int anchor = 0, start = 0, end = 0;
    long long sum = 0, maxSum = 0;

    for (int i=0; i<A.size(); i++) {
        if (A[i] < 0) {
            // If element is negative, update sum and range
            anchor = i+1;
            sum = 0;
        } else {
            // If element is positive, update sum and range
            sum += A[i];
            if (sum > maxSum) {
                start = anchor;
                end = i+1;
                maxSum = sum;
            } else if (sum == maxSum) {
                if (i + 1 - anchor > end - start) {
                    end = i + 1;
                    start = anchor;
                }
            }
        }
    }

    vector<int> ans;
    while (start < end) {
        ans.push_back(A[start++]);
    }
    return ans;
}

results matching ""

    No results matching ""