Find the contiguous subarray within an array (containing at least one number) which has the largest product.
For example, given the array
the contiguous subarray
[2,3,-2,4]
,the contiguous subarray
[2,3]
has the largest product = 6
.
Solution 1: Use DP and optimize the space to O(1), keep both max and min product, sometimes negtive number mult
public class Solution {
public int maxProduct(int[] nums) {
int n=nums.length;
int max=0, min=0, res=0;
for (int i=0; i<n; i++) {
if (i==0) {
max=nums[i];
min=nums[i];
res=nums[i];
}
else {
int maxNew=Math.max(nums[i],Math.max(nums[i]*max,nums[i]*min));
min=Math.min(nums[i],Math.min(nums[i]*max,nums[i]*min));
max=maxNew;
res=Math.max(res,max);
}
}
return res;
}
}
没有评论:
发表评论