Orange-Bloom/Max Non Negative Subarray.java at master · aky91/Orange-Bloom · GitHub

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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
//https://www.interviewbit.com/problems/max-non-negative-subarray/

public class Solution {

    public ArrayList<Integer> maxset(ArrayList<Integer> A) {

        int N = A.size();

        long max = -1;
        int start = -1;
        int end = -1;

        long sum = 0;
        int s = -1;

        boolean flow = false;
        boolean allNeg = true;

        for(int i = 0; i <= N; i++){

            int num;

            if(i == N)
                num = -1;
            else
                num = A.get(i);

            if(num >= 0){

                allNeg = false;

                if(flow == false){
                    flow = true;
                    s = i;
                }

                sum += num;

            } else {

                flow = false;

                if(sum > max ){
                    start = s;
                    end = i - 1;
                    max = sum;
                }

                sum = 0;
            }
        }

        ArrayList<Integer> ans = new ArrayList<>();

        if(allNeg)
            return ans;

        for(int i = start; i <= end; i++)
            ans.add(A.get(i));

        return ans;
    }
}