给定一个整数数组
nums，找出一个序列中乘积最大的连续子序列（该序列至少包含一个数）。示例 1:
输入: [2,3,-2,4] 输出:6解释: 子数组 [2,3] 有最大乘积 6。示例 2:
输入: [-2,0,-1] 输出: 0 解释: 结果不能为 2, 因为 [-2,-1] 不是子数组。
解法一：
//时间复杂度O(n), 空间复杂度O(1)
class Solution {
public:
int maxProduct(vector<int>& nums) {
int res = INT_MIN;
int maxP = 1, minP = 1;
for(int num : nums) {
if(num < 0) swap(maxP, minP);
maxP = max(num, maxP * num);
minP = min(num, minP * num);
res = max(maxP, res);
}
return res;
}
};解法一：
动态规划。设置一个数组dp[n]，其中dp[i]代表数组中前i项组成的序列所能得到的最大子序列乘积，题上要求序列至少1个元素，显然dp[0] = nums[0]。
如果nums中元素非负，很容易想出其递推关系为dp[i] = max(num, dp[i - 1] * num);。为了节省空间，可以只记录上一步的dp，也就是maxP。
问题在于nums中有负数，负负得正，那我们需要维护一个最小值minP，如果遇到负数，就交换maxP和minP。
2019/12/30 00:00