LeetCode Maximum Product Subarray

152. Maximum Product Subarray

Given an integer array nums, find the contiguous subarray within an array (containing at least one number) which has the largest product.

Example 1:

Input: [2,3,-2,4]
Output: 6
Explanation: [2,3] has the largest product 6.

Example 2:

Input: [-2,0,-1]
Output: 0
Explanation: The result cannot be 2, because [-2,-1] is not a subarray.

本题要求一个数组中最大的连续子数组的积,和LeetCode Maximum Subarray很类似,后者是求最大连续子数组的和。
但是因为乘积有其独特性,即负负得正,所以即使前面算到有很大的负数,也不能舍弃,万一后面来一个负数,负负得正就会得到很大的正数。
本题也是使用动态规划来做。维护两个变量,令curMax和curMin分别表示当前最大连续乘积值和最小连续乘积值。则有
curMax = max(curMax*nums[i], curMin*nums[i], nums[i]);
curMin = min(curMax*nums[i], curMin*nums[i], nums[i]);
很好理解,不解释:

class Solution {
  public: int maxProduct(vector < int > & nums) {
    int ans = nums[0], curMax = nums[0], curMin = nums[0];
    for (size_t i = 1; i < nums.size(); ++i) {
      int tmp = curMax;
      curMax = max(max(curMax * nums[i], curMin * nums[i]), nums[i]);
      curMin = min(min(tmp * nums[i], curMin * nums[i]), nums[i]);
      ans = max(ans, curMax);
    }
    return ans;
  }
};

本代码提交AC,用时6MS。

再细究一下,假设curMax和curMin为当前最大最小连续乘积值,且规定curMax一定是正数。则当nums[i]为正数时,curMax更新为curMax*nums[i],无论curMin是否为正,curMin都更新为curMin*nums[i]。
当nums[i]为负数时,curMax更新为curMin*nums[i],curMin更新为curMax*nums[i]。因为curMax一定为正,所以curMax*nums[i]一定为负。即使curMin也为正,但curMin<curMax,所以curMin*nums[i]>curMax*nums[i]。如果curMin为负,则curMin*nums[i]为正,更大于curMax*nums[i]了。
这种思路就分析得比较细致,注意代码第6行需要记录前一次的最大值,因为运算过程中curMax有可能是0或者负数,为了保证curMax一定是正数的性质,需要第6行(比如输入为0,2,则i=0运算完之后curMax=curMin=0;当i=1时,如果第8行curMax*=nums[i],则curMax还是0)。且因为第12行会更新curMax,而第13行需要用到上一次的最大值。
完整代码如下:

class Solution {
  public: int maxProduct(vector < int > & nums) {
    int ans = nums[0], curMax = 1, curMin = 1;
    for (size_t i = 0; i < nums.size(); ++i) {
      int oldMax = max(curMax, 1);
      if (nums[i] > 0) {
        curMax = oldMax * nums[i];
        curMin *= nums[i];
      } else {
        curMax = curMin * nums[i];
        curMin = oldMax * nums[i];
      }
      ans = max(ans, curMax);
    }
    return ans;
  }
};

本代码提交AC,用时也是6MS。

Leave a Reply

Your email address will not be published. Required fields are marked *