Medium
自己写的two pointers对大数据input会TLE, 是O(N2)的time complexity
答案用的其实是动态规划.
maxProduct和minProduct分别记录以nums[i]结尾的subArray里乘积最大／最小值.每次更新的时候，要注意正负号带来的最大值可能变最小、最小值可能变最大这样的情况，所以要比较三个值的大小.
class Solution {
public int maxProduct(int[] nums) {
int maxProduct = 1;
int minProduct = 1;
int res = Integer.MIN_VALUE;
for (int i = 0; i < nums.length; i++){
int temp = maxProduct;
//maxProduct/minProduct stores the max/min product of
//subarray that ends with the current number nums[i]
maxProduct = Math.max(Math.max(maxProduct*nums[i], minProduct*nums[i]), nums[i]);
minProduct = Math.min(Math.min(temp*nums[i], minProduct*nums[i]), nums[i]);
if (maxProduct > res){
res = maxProduct;
}
}
return res;
}
}
