[每日leetcode]乘积最大子序列

给定一个整数数组 nums ，找出一个序列中乘积最大的连续子序列（该序列至少包含一个数）。

示例 1:

输入: [2,3,-2,4] 输出: 6 解释: 子数组 [2,3] 有最大乘积 6。 示例 2:

输入: [-2,0,-1] 输出: 0 解释: 结果不能为 2, 因为 [-2,-1] 不是子数组。

解析

最大乘积可以由正数正数和负数负数得到，因此，需要同时记录下最大值和最小值。

状态定义：

f(x) -------- nums数组中[0, x]范围内的最大连续子序列的乘积，且该连续子序列以nums[x]结尾 g(x) -------- nums数组中[0, x]范围内的最小连续子序列的乘积，且该连续子序列以nums[x]结尾

状态转移：

（1）当x等于0时，显然此时[0, x]范围内只有一个元素，f(0)和g(0)均等于这个唯一的元素。 （2）当x大于0时

a：如果nums[x] >= 0，f(x) = max(f(x - 1) * nums[x], nums[x])，g(x) = min(g(x - 1) * nums[x], nums[x])

b：如果nums[x] < 0，f(x) = max(g(x - 1) * nums[x], nums[x])，g(x) = min(f(x - 1) * nums[x], nums[x])

class Solution { public: int maxProduct(vector<int>& nums) { vector<int> dpmax(nums.size(),0); vector<int> dpmin(nums.size(),0); dpmax[0]=dpmin[0]=nums[0]; for(int i=1;i<nums.size();i++) { if(nums[i]>=0) { dpmax[i]=max(dpmax[i-1]*nums[i],nums[i]); dpmin[i]=min(dpmin[i-1]*nums[i],nums[i]); } else { dpmax[i]=max(dpmin[i-1]*nums[i],nums[i]); dpmin[i]=min(dpmax[i-1]*nums[i],nums[i]); } } int result=INT_MIN; for(int i=0;i<dpmax.size();i++) { if(dpmax[i]>result) result=dpmax[i]; } return result; } };

参考https://blog.csdn.net/qq_41231926/article/details/86261978