Find the contiguous subarray within an array (containing at least one number) which has the largest product.
For example, given the array [2,3,-2,4],
the contiguous subarray [2,3] has the largest product = 6.
一刷
题解：求最大乘积子数组。 依然是用Dynamic Programming的思想，不过这回我们要维护一个max以及一个min。注意，当当前num[i]为负数时，max和min交换。
Time Complexity - O(n)， Space Complexity - O(1)。
public class Solution {
public int maxProduct(int[] nums) {
if(nums == null || nums.length == 0)
return 0;
int res = nums[0], max = nums[0], min = nums[0];
for(int i = 1; i < nums.length; i++) {
if(nums[i] > 0) {
max = Math.max(nums[i], nums[i] * max);
min = Math.min(nums[i], nums[i] * min);
} else {
int max_copy = max;
max = Math.max(nums[i], nums[i] * min);
min = Math.min(nums[i], nums[i] * max_copy);
}
res = Math.max(res,max);
}
return res;
}
}
二刷
首先思考，当长度增1，是不是可以利用之前的解，如果可以的话，就是DP问题。
之前的解，最大值和最小值都要保存下来，因为如果当前是负数，那么最大值就变成了最小值。
public class Solution {
public int maxProduct(int[] nums) {
int max = nums[0], min = nums[0], res = nums[0];
for(int i=1; i<nums.length; i++){
if(nums[i]>0){
max = Math.max(nums[i], max*nums[i]);
min = Math.min(nums[i], min*nums[i]);
}
else{
int min_copy = min;
min = Math.min(nums[i], max*nums[i]);
max = Math.max(nums[i], min_copy*nums[i]);
}
res = Math.max(max, res);
}
return res;
}
}
