### 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<Integer> maxset(ArrayList<Integer> 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;i<A.size();i++){ if(A.get(i)<0){ tmp_start = i+1; tmp_end = i+1; tmp_sum = 0; }else{ tmp_sum += A.get(i); if(tmp_sum>sum){ 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<Integer> res = new ArrayList<Integer>(); if(start == -1) return res; for(int i=start; i<=end;i++){ res.add(A.get(i)); } return res; } } |

**Other Posts You May Like**

## Comments

## Post a Comment