C++刷LeetCode（152. 乘积最大子数组）【动态规划*】
题目描述：给你一个整数数组 nums ，请你找出数组中乘积最大的连续子数组（该子数组中至少包含一个数字），并返回该子数组所对应的乘积。
示例 1:
输入:
输出: 6
解释: 子数组 有最大乘积 6。
示例 2:
输入: [-2,0,-1]
输出: 0
解释: 结果不能为 2, 因为 [-2,-1] 不是子数组。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/maximum-product-subarray
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
class Solution {
public:
int maxProduct(vector<int>& nums) {
int len = nums.size();
if(len == 0)return 0;
int res = nums;
int min_temp = nums;
int max_temp = nums;
for(int i = 1; i < len; i++){
int store = min_temp;
min_temp = min(min(nums, max_temp * nums), min_temp * nums);//nums决定了可以从i处开始
max_temp = max(max(nums, max_temp * nums), store * nums);
res = max(res, max_temp);
}
return res;
}
};
参考链接：https://leetcode-cn.com/problems/maximum-product-subarray/solution/dpfang-fa-xiang-jie-by-yang-cong-12/
页:
[1]