152. 乘积最大子序列

题目:

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

示例 1:

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

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

 

代码:

 1 class Solution {
 2 public:
 3     int maxProduct(vector<int>& nums) {
 4 
 5         int n = nums.size();
 6         if(n == 1)
 7             return nums[0];
 8         int ret = nums[0];
 9         int curMax = nums[0];
10         int curMin = nums[0];
11         for(int i = 1;i < n;i++)
12         {   //当前位置和pre“接起来”能产生的最小连续子序列之积
13             int temp1 = min(nums[i]*curMin,nums[i]*curMax);
14             //当前位置和pre“接起来”能产生的最大连续子序列之积
15             int temp2 = max(nums[i]*curMin,nums[i]*curMax);
16             //以当前位置结尾的最小连续子序列之积
17             curMin = min(nums[i],temp1);
18             //以当前位置结尾的最大连续子序列之积
19             curMax = max(nums[i],temp2);
20             ret = max(curMax,ret);
21         }
22         return ret;       
23     }
24 };

 

上一篇:LC1043. Partition Array for Maximum Sum


下一篇:leetcode1031