题目描述
Given an integer array nums, find the contiguous subarray within an array (containing at least one number) which has the largest product.
Example1:
Input: [2,3,-2,4]
Output: 6
Explanation: [2,3] has the largest product 6.
Example1:
Input: [-2,0,-1]
Output: 0
Explanation: The result cannot be 2, because [-2,-1] is not a subarray.
dp解题思路
- 这题也是要用dp的思想，有一点特殊，需要记住本次的最大值，最小值 -》用来更新下次的最大值 最小值
- pre_max, pre_min, // 上次的最大值，最小值，乘以一个负数时，最大值变最小值，最小值变最大值；
- cur_max, cur_min, // 本次的最大值，最小值，本次的最大值，就有可能是最后的结果。
- cur_max = max(nums[i], max(pre_max * nums[i], pre_min * nums[i]))
- cur_min = min(nums[i], max(pre_max * nums[i], pre_min * nums[i]))
- 然后将 cur_max, cur_min进行赋值给 pre_max, pre_min
class Solution {
public:
int maxProduct(vector<int>& nums) {
// dp[i] = max(nums[i], max(cur * pre_max, cur * pre_min));
int cur_max = 1;
int cur_min = 1;
int pre_max = 1;
int pre_min = 1;
int res = INT_MIN;
for(int i = 0; i < nums.size(); i++){
cur_max = max(nums[i], max(pre_max * nums[i], pre_min * nums[i]));
cur_min = min(nums[i], min(pre_max * nums[i], pre_min * nums[i]));
res = max(res, cur_max);
pre_max = cur_max;
pre_min = cur_min;
}
return res;
}
};
