【leetcode】152. 乘积最大子数组

题目内容

思路分析

方法一：动态规划

本题与53. 最大子序和类似，但是本题是乘法运算，因此nums[i]的最大乘积不一定依赖于前一个数字（如[-1, 2, -3, 4]）。因此需要利用以下关系来进行动态规划：

当前最大值 = max(上一个数的最大值*当前数, 上一个数的最小值*当前数, 当前数)
当前最小值 = min(上一个数的最大值*当前数, 上一个数的最小值*当前数, 当前数)

代码

#include <vector>
#include <math.h>
#include <limits.h>

using namespace std;

// 动态规划
// 时间复杂度O(n)
// 空间复杂度O(1)
class Solution {
public:
    int maxProduct(vector<int>& nums) {
       int n = nums.size();
       if (n == 0) return 0;

       int last_max_product{ nums[0] }, last_min_product{ nums[0] };
       int max_product = last_max_product;
       int min_product = last_min_product;
       int max_product_all = max_product;

       for (int i = 1; i < n; ++i) {
          max_product = max(max(last_max_product * nums[i], 
            last_min_product * nums[i]), nums[i]);
          min_product = min(min(last_max_product * nums[i], 
            last_min_product * nums[i]), nums[i]);
          last_max_product = max_product;
          last_min_product = min_product;
          max_product_all = max(max_product_all, max_product);
       }

       return max_product_all;
    }
};

int main() {
   Solution s;
   vector<int> input{ -2,0,-1 };
   int result = s.maxProduct(input);
   int a = 0;
}

收获

感觉自己对于已经掌握的方法应用还不是很灵活。