乘积最大子序列

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

示例 1:

输入: [2,3,-2,4]

输出: 6

解释: 子数组 [2,3] 有最大乘积 6。

示例 2:

输入: [-2,0,-1]

输出: 0

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

解题思路：乘法与加法最大差别在于，当前元素的符号具有全局性的作用。

如果当前元素为负，那么连乘到上个元素的最大乘积，再乘以当前元素，就变成负数，甚至可能成为最小乘积。

同样，连乘到上个元素的最小乘积如为负，再乘以当前元素，就变成正数，甚至可能成为最大乘积。

因此使用动态规划的方法：

记maxLast/minLast为连乘到上个元素的最大/小乘积

记maxCur/minCur为连乘到当前元素的最大/小乘积

记maxAll为全局最大乘积

 class Solution{

 public:

     int maxProduct(vector<int>& nums){

         if (nums.empty()){

             return 0;

         }

         if (nums.size() == 1){

             return nums[0];

         }

         int maxAll = nums[0];//global maximum

         int maxLast = nums[0];//maximum including last element

         int maxCur;//maximum including current element

         int minLast = nums[0];//minumum including current element

         int minCur;//minimum including last element

         for (int i = 1; i<nums.size(); i++){

             maxCur = max(nums[i], max(maxLast*nums[i], minLast*nums[i]));

             minCur = min(nums[i], min(maxLast*nums[i], minLast*nums[i]));

             maxLast = maxCur;

             minLast = minCur;

             maxAll = max(maxAll, maxCur);

         }

         return maxAll;

     }

 };

巴特西

Leetcode 152.乘机最大子序列

乘积最大子序列

最新文章

热门文章