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.

由于负数的存在，需要同时保存当前最大值和当前最小值，所以需要维护两个DP表，可以分别表示为dp_min和dp_max。所以即为dp_max里的最大值。

需要维护的当前最大值和当前最小值，都是在dp_min[i-1] * A[i]，dp_max[i] * A[i]，和A[i]这三者里面取一即可。有了这个只关乎最终状态，不关乎过程细节的结论，解题过程可以大大简化。

  class Solution {

  public:

      int maxProduct(vector<int>& nums) {

           int n = nums.size();

           if(n==) return ;

           vector<int>dp_max(n,nums[]);

           vector<int>dp_min(n,nums[]);

           int res_val = nums[];

          for(int i =;i<n;i++){

              dp_max[i] = std::max( std::max(dp_max[i-]*nums[i],dp_min[i-]*nums[i]),    nums[i]);

              dp_min[i]= std::min( std::min(dp_min[i-]*nums[i],dp_max[i-]*nums[i]),    nums[i]);

          }

          for(int i =;i<n;i++)

                 res_val = std::max(dp_max[i],res_val);

          return res_val;

      }

  };

思考以上DP解法的空间开销过大的原因，是因为保存了整个DP表。其实整个过程中，获得dp[i]的值只需要dp[i-1]的值，所以是不需要保存整个DP表的。

这样一来，DP可以用滚动数组进行优化。简单的写法其实就是设一对prevMin/prevMax表示上一个值，以及还有一对curMin/curMax表示当前值。

 class Solution {

 public:

     int maxProduct(vector<int>& nums) {

         int n = nums.size();

         if(n==) return ;

         int dp_max_pre = nums[];

         int dp_min_pre = nums[];

         int dp_max;

         int dp_min;

         int res_val = nums[];

         for(int i =;i<n;i++){

             dp_max = std::max( std::max(dp_max_pre*nums[i],dp_min_pre*nums[i]),    nums[i]);

             dp_min= std::min( std::min(dp_max_pre*nums[i],dp_min_pre*nums[i]),    nums[i]);

             res_val =std::max(res_val,dp_max);

             dp_max_pre = dp_max;

             dp_min_pre = dp_min;

         }

         return res_val;

     }

 };

巴特西

152. Maximum Product Subarray（动态规划）

最新文章

热门文章