Learn_Java/loops/MaximumSumSubarray.java at master · imkss/Learn_Java · 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
package loops;

public class MaximumSumSubarray {

	public static void main(String[] args) {
		int a[] = {-1, 4, -2, 4, -1, 3, 5, -6};
//		int max = Integer.MIN_VALUE;
		int n = a.length;

		int maxSum = Integer.MIN_VALUE;
		int curSum = 0;
		for(int i = 0; i < n; i++) {

			curSum += a[i];

			if(curSum >  maxSum) {
				maxSum = curSum;
			}
			if(curSum < 0) {
				curSum = 0;
			}

		}
		System.out.println(maxSum);


//		int sum[] = new int [n];
//		sum[0] = a[0];
//		for(int i = 1; i < n; i++) {
//			sum[i] = sum[i-1] + a[i];
//		}
//		for(int i = 0; i < n; i++) {
//			for(int j = i; j < n; j++) {
//				int curSum = sum[j] - sum[i] + a[i];
//				if(curSum > max) {
//					max = curSum;
//				}
//			}
//		}
//
////		for(int i = 0; i < n; i++) {
////			for(int j = i; j < n; j++) {
////				int curSum = 0;
////				for(int k = i; k <= j; k++) {
////					curSum += a[k];
////				}
////				if(curSum > max) {
////					max = curSum;
////				}
////			}
////		}
//		System.out.println(max);
	}
}