Max Non Negative SubArray

Given an array of integers, A of length N, find out the maximum sum sub-array of non negative numbers from A.

The sub-array should be contiguous i.e., 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.

Find and return the required subarray.

NOTE:

1. If there is a tie, then compare with segment's length and return segment which has maximum length.

2. If there is still a tie, then return the segment with minimum starting index.

Problem Constraints

1 <= N <= 105 -109 <= A[i] <= 109

Input Format

he first and the only argument of input contains an integer array A, of length N.

Output Format

Return an array of integers, that is a subarray of A that satisfies the given conditions. Example Input

Input 1:

 A = [1, 2, 5, -7, 2, 3]

Input 2:

 A = [10, -1, 2, 3, -4, 100]

Example Output

Output 1:

 [1, 2, 5]

Output 2:

 [100]

Example Explanation

Explanation 1:

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

Explanation 2:

 The three sub-arrays are [10], [2, 3], [100].
 The answer is [100] as its sum is larger than the other two.

public class Solution {
    public int[] maxset(int[] A) {
        int maxLen = 0;
        long maxSum = 0;
        int maxStart = 0;
        int start = 0;
        long currentSum = 0;
        int currentlen = 0;
        for (int i = 0; i < A.length; i++) {
            if (A[i] < 0) {
                if (currentSum > maxSum) {
                    maxSum = currentSum;
                    maxLen = currentlen;
                    maxStart = start;
                } else if (currentSum == maxSum) {
                    if (currentlen > maxLen) {
                        maxLen = currentlen;
                        maxStart = start;
                    }
                }
                start = i + 1;
                currentlen = 0;
                currentSum = 0;
            } else {
                currentSum += (long) A[i];
                currentlen++;
            }
        }
        if (currentSum > maxSum) {
            maxSum = currentSum;
            maxLen = currentlen;
            maxStart = start;
        } else if (currentSum == maxSum) {
            if (currentlen > maxLen) {
                maxLen = currentlen;
                maxStart = start;
            }
        }
        int[] ans = new int[maxLen];
        for (int i = maxStart; i < (maxStart + maxLen); i++) 
            ans[i - maxStart] = A[i];
        return ans;
    }
}