152. 乘积最大子序列

1、题目描述

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

示例 1:

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

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

2、题解

2.1 思路分析

求数组中子区间的最大乘积，在这里使用动态规划去做。

对重要的是找出DP方程：

对于一个数组，因为可能存在负数，我们保存当前位置的最大乘积和最小乘积

因为负数可以将最大乘积变最小，将最小乘积变最大。

初始化结果 res = MIN 。当前最大乘积max_num = 1 ,当前最小乘积min_num = 1。
遍历数组[0,n]：　　
若num[i] < 0：交换最大乘积与最小乘积的值
max_num=max(max_num∗nums[i],nums[i])，更新当前位置的最大乘积。
min_num=min(min_num∗nums[i],nums[i])，更新当前位置的最小乘积。
更新结果 res = max(max_num,res)
返回res

2.2 python题解

 1 class Solution:
 2     def maxProduct(self, nums: List[int]) -> int:
 3         n = len(nums)
 4         
 5         maxnum = 1
 6         minnum = 1
 7         res = -float("inf")  #把 res 设置为负无穷
 8         for i in range(n):
 9             if(nums[i]<0):
10                 maxnum,minnum = minnum,maxnum
11             maxnum = max(maxnum*nums[i],nums[i])
12             minnum = min(minnum*nums[i],nums[i])
13             res = max(maxnum,res)
14         return res

2.3 C++题解

 1 class Solution {
 2 public:
 3     int maxProduct(vector<int>& nums) {
 4         int n = nums.size();
 5         if(n==0) return 0;
 6         else if(n==1) return nums[0];
 7         int p = nums[0];
 8         int maxP = nums[0];
 9         int minP = nums[0];
10        for(int i = 1;i<n;i++)
11         {
12             int t = maxP;
13             maxP = max(max(maxP  * nums[i],nums[i]),minP*nums[i]);
14             minP = min(min(t*nums[i],nums[i]),minP*nums[i]);
15             p = max(maxP,p);
16         }
17         return p;
18     }
19 };