HackerEarth/ArraySubsetSumMax.java at main · hmanshug/HackerEarth · 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
64
65
66
67
68
69
70
71
72
73
74
75
76
package he;

import java.util.ArrayList;

public class ArraySubsetSumMax {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		System.out.println();

	}
	public ArrayList<Integer> maxset(ArrayList<Integer> a) {


	    int len=a.size(), left=0, right=0, i=0;
	    long fsum=-1, sum=0;
	    int fleft=-1, fright=-1;
	    ArrayList<Integer> temp= new ArrayList<>();
	    boolean flag=false;

	    for(i=0; i<len; i++) { // negative
	        if(a.get(i)<0) {
	            if(flag==true) {
	                right=i-1;
	                if(fsum<sum) {
	                    fsum=sum;
	                    fleft=left;
	                    fright=right;
	                } else if(fsum==sum) {
	                    int flen=fright=fleft+1, nlen=right-left+1;
	                    if(flen<nlen) {
	                        fsum=sum;
    	                    fleft=left;
    	                    fright=right;
	                    }
	                }

	                sum=0;
	            }
	            flag=false;

	        } else if(flag==true){ // positive repeat
	            sum+=a.get(i);

	        } else { //first positive
	            sum=a.get(i);
	            left=i;
	            flag=true;
	        }
	    }
	    if(flag==true) {
            right=i-1;
            if(fsum<sum) {
                fsum=sum;
                fleft=left;
                fright=right;
            } else if(fsum==sum) {
                int flen=fright=fleft+1, nlen=right-left+1;
                if(flen<nlen) {
                    fsum=sum;
                    fleft=left;
                    fright=right;
                }
            }

            sum=0;
        }
        if(fsum!=-1)
	    for(int j=fleft; j<=fright; j++) {
	    	temp.add(a.get(j));
	    }
		return temp;


	}
}