LeetCode-Solutions-in-Cpp17

Solutions to high-frequency interview questions of LeetCode in C++17, taking into account both efficiency and comprehensibility.

---

Project maintained by downdemo Hosted on GitHub Pages — Theme by mattgraham

• 动态规划，dp[i] 表示以 nums[i - 1] 为子序列结尾的最大乘积。由于可能存在负数，最小负数乘负数也可能为最大乘积，因此需要多一个数组，记录以 nums[i - 1] 为结尾的最小乘积

class Solution {
 public:
  int maxProduct(vector<int>& nums) {
    int sz = size(nums);
    vector<int> dpMax(sz + 1, INT_MIN);
    vector<int> dpMin(sz + 1, INT_MAX);
    dpMin[0] = 1;
    dpMax[0] = 1;
    int res = INT_MIN;
    for (int i = 0; i < sz; ++i) {
      int a = dpMax[i] * nums[i];
      int b = dpMin[i] * nums[i];
      dpMax[i + 1] = max({a, b, nums[i]});
      dpMin[i + 1] = min({a, b, nums[i]});
      res = max(res, dpMax[i + 1]);
    }
    return res;
  }
};

• 动态规划数组可以优化掉

class Solution {
 public:
  int maxProduct(vector<int>& nums) {
    int mx = 1;
    int mn = 1;
    int res = INT_MIN;
    for (auto& x : nums) {
      if (x < 0) {
        swap(mx, mn);
      }
      mx = max(mx * x, x);
      mn = min(mn * x, x);
      res = max(res, mx);
    }
    return res;
  }
};