Given an integer array nums, find the contiguous subarray within an array (containing at least one number) which has the largest product.
Example 1:
Input: [2,3,-2,4]
Output: 6
Explanation: [2,3] has the largest product 6.
Example 2:
Input: [-2,0,-1]
Output: 0
Explanation: The result cannot be 2, because [-2,-1] is not a subarray.
Solution & Code
class Solution {
// 用max sum subarray的思路托嚣， DP
// 但是不能只求maxSubarray Array,因為乘法有正負，負負為正蒜茴，所以不能只簡單取
// preProductArray [i] = Math.max (preProductArray [i - 1] * nums[i], nums[i]);
// max = Math.max (preProductArray [i], max);
// eg. [-2, 3, -4]浇冰。如果只上述算，那么結(jié)果就是3洋魂，因為到了3的時候绷旗，-6就被舍棄了喜鼓。
// 所以Idea是，keep max and min for current index, and keep it for the next iteration
public int maxProduct(int[] nums) {
if (nums == null || nums.length == 0)
return 0;
int maxProduct = nums[0];
int minProduct = nums[0];
int maxResult = nums[0];
for (int i = 1; i < nums.length; i++) {
int maxTemp = maxProduct;
maxProduct = Math.max (Math.max (maxProduct * nums[i], nums[i]), minProduct * nums[i]);
minProduct = Math.min (Math.min (minProduct * nums[i], nums[i]), maxTemp * nums[i]);
maxResult = Math.max (maxResult, maxProduct);
}
return maxResult;
}
}
