-
Notifications
You must be signed in to change notification settings - Fork 2
/
MaximumProductSubarray.java
32 lines (30 loc) · 1.26 KB
/
MaximumProductSubarray.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
package src.java.medium.array;
public class MaximumProductSubarray {
// Optimize space usage
public int maxProduct(int[] nums) {
int ret = nums[0];
int minEnding = nums[0], maxEnding = nums[0];
for (int i=1; i<nums.length; i++) {
int min = Math.min(minEnding*nums[i], maxEnding*nums[i]);
int max = Math.max(minEnding*nums[i], maxEnding*nums[i]);
minEnding = Math.min(nums[i], min);
maxEnding = Math.max(nums[i], max);
ret = Math.max(ret, maxEnding);
}
return ret;
}
public int maxProduct2(int[] nums) {
if (nums == null || nums.length == 0) return 0;
int ret = nums[0];
int[] maxProductEndHere = new int[nums.length];
int[] minProductEndHere = new int[nums.length];
maxProductEndHere[0] = nums[0];
minProductEndHere[0] = nums[0];
for (int i=1; i<nums.length; i++) {
maxProductEndHere[i] = Math.max(Math.max(maxProductEndHere[i-1]*nums[i], minProductEndHere[i-1]*nums[i]), nums[i]);
minProductEndHere[i] = Math.min(Math.min(maxProductEndHere[i-1]*nums[i], minProductEndHere[i-1]*nums[i]), nums[i]);
ret = Math.max(maxProductEndHere[i], ret);
}
return ret;
}
}