152. maxProduct

分析

• 使用f[i - 1]记录所有以nums[i - 1]元素结尾的连续子数组中的最大乘积

• 使用g[i - 1]记录所有以nums[i - 1]元素结尾的连续子数组中的最小乘积

• 求f[i]

  • 当nums[i]为正数时，f[i] = std::max(nums[i], f[i - 1] * nums[i])，因为正数与最大值相乘，值最大，所以与f[i - 1]相乘
  • 当nums[i]为负数时，f[i] = std::max(nums[i], g[i - 1] * nums[i])，因为负数与最小值相乘，值最大，所以与g[i - 1]相乘

• 求g[i]

  • 当nums[i]为正数时，g[i] = std::min(nums[i], g[i - 1] * nums[i])，因为正数与最小值相乘，值最小，所以与g[i - 1]相乘
  • 当nums[i]为负数时，g[i] = std::min(nums[i], f[i - 1] * nums[i])，因为负数与最大值相乘，值最小，所以与f[i - 1]相乘

• 当nums[i]为0时，f[i]和g[i]都变为0，即连续子数组断开，从下一个元素重新开始找最大乘积

优化：因为每次更新f[i]和g[i]只需要前一个数，所以不需要开两个数组记录所有值

时间复杂度：O(n)

C++代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution {
public:
    int maxProduct(vector<int>& nums)
    {
      int res = nums[0];
      int f_last = nums[0], g_last = nums[0];
      for (int i = 1; i < nums.size(); ++ i)
      {
        int f_cur = f_last * nums[i], g_cur = g_last * nums[i];
        f_last = std::max(nums[i], std::max(f_cur, g_cur));
        g_last = std::min(nums[i], std::min(f_cur, g_cur));
        res = std::max(res, f_last);
      }
      return res;
    }
};