-
Notifications
You must be signed in to change notification settings - Fork 0
/
MaximumSubarray.java
49 lines (48 loc) · 1.69 KB
/
MaximumSubarray.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
38
39
40
41
42
43
44
45
46
47
48
49
public class MaximumSubarray {
// public static int maxSubArray(int[] nums) {
// return maxSubArray(nums, 0, nums.length - 1);
// }
// public static int maxSubArray(int[] nums, int left, int right) {
// if (left > right) {
// return Integer.MIN_VALUE;
// } else if (left == right) {
// return nums[left];
// } else {
// int middle = (right - left) / 2 + left;
// int leftMax = maxSubArray(nums, left, middle);
// int rightMax = maxSubArray(nums, middle + 1, right);
// int sum = 0;
// int maxToLeft = Integer.MIN_VALUE;
// for (int i = middle; i >= left; i--) {
// sum += nums[i];
// maxToLeft = Math.max(maxToLeft, sum);
// }
// sum = 0;
// int maxToRight = Integer.MIN_VALUE;
// for (int i = middle + 1; i <= right; i++) {
// sum += nums[i];
// maxToRight = Math.max(maxToRight, sum);
// }
// int result = maxToLeft + maxToRight;
// result = Math.max(result, leftMax);
// result = Math.max(result, rightMax);
// return result;
// }
// }
public static int maxSubArray(int[] nums) {
int result = nums[0];
int sum = nums[0];
for (int i = 1; i < nums.length; i++) {
if (sum < 0) {
sum = 0;
}
sum += nums[i];
result = Math.max(result, sum);
}
return result;
}
public static void main(String[] args) {
int[] nums = {1, 2, -6, 3, -2, 4, -1, 3, 2, -4};
System.out.println(maxSubArray(nums));
}
}