Max Non Negative SubArray - The Coding Shala

Home >> Interview Questions >> Max non-negative subarray

Max Non-Negative SubArray InterviewBit Solution

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 elements and skipping the third element is invalid.

The 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: (Java)

 ``` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37``` ```public class Solution { public ArrayList maxset(ArrayList A) { int start = -1; int end = -1; int tmp_start = 0, tmp_end = 0; long sum = Integer.MIN_VALUE; long tmp_sum = 0; for(int i=0;isum){ start = tmp_start; end = i; sum = tmp_sum; } else if(tmp_sum == sum && (tmp_end-tmp_start > end-start)){ start = tmp_start; end = i; sum = tmp_sum; } tmp_end++; } } // System.out.println(start+" "+end); ArrayList res = new ArrayList(); if(start == -1) return res; for(int i=start; i<=end;i++){ res.add(A.get(i)); } return res; } } ```

Other Posts You May Like