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).
Max Non Negative SubArray Java Program - The Coding Shala
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
Please leave a comment below if you like this post or found some error, it will help me to improve my content.

Comments

Popular Posts from this Blog

Anti Diagonals - The Coding Shala

Shell Script to find sum, product and average of given numbers - The Coding Shala

LeetCode - Bulb Switcher Solution - The Coding Shala

New Year Chaos Solution - The Coding Shala

Sorting the Sentence LeetCode Solution - The Coding Shala