HHot 100C++ 图解

152. 乘积最大子数组

中等 动态规划(一维) 4 帧动画 在力扣上做

一句话套路同时维护最大积与最小积,遇负交换

题目描述

给你一个整数数组 nums ,请你找出数组中乘积最大的非空连续 子数组(该子数组中至少包含一个数字),并返回该子数组所对应的乘积。

测试用例的答案是一个 32-位 整数。

请注意,一个只包含一个元素的数组的乘积是这个元素的值。

 

示例 1:

输入: nums = [2,3,-2,4]
输出: 6
解释: 子数组 [2,3] 有最大乘积 6。

示例 2:

输入: nums = [-2,0,-1]
输出: 0
解释: 结果不能为 2, 因为 [-2,-1] 不是子数组。

 

提示:

  • 1 <= nums.length <= 2 * 104
  • -10 <= nums[i] <= 10
  • nums 的任何子数组的乘积都 保证 是一个 32-位 整数

思路

时间O(n)
空间O(1)

关键

乘法会把「最小」变成「最大」(负负得正),所以必须同时维护以 i 结尾的最大积 curMax 和最小积 curMin,遇到负数时两者交换。

易错

初值必须是 nums[0] 而不是 0 或 1:

  • · 初值 0 -> 全负数组(如 [-2])会返回 0(错,应为 -2);
  • · 初值 1 -> 相当于允许「什么都不选」。

对比

Q53 最大子数组和只需要一个 cur(负了就归零),这题不行 —— 这就是负数的威力。

图解

2 0 -5 1 -2 2 -4 3 3 4
数组(来自本仓库测试数据,下标从 0 开始)

逐帧动画

1 / 4

快捷键:← → 单步,空格播放 / 暂停。

C++17 题解

src/15_dp.cpp17 行
namespace lc0152 {
class Solution {
 public:
  int maxProduct(vector<int>& nums) {
    if (nums.empty()) return 0;  // 题面保证 n >= 1;nums[0] 不能裸取
    int ans = nums[0], curMax = nums[0], curMin = nums[0];
    for (size_t i = 1; i < nums.size(); ++i) {
      int x = nums[i];
      if (x < 0) swap(curMax, curMin);  // 乘负数会让大小关系翻转
      curMax = max(x, curMax * x);      // 要么从 x 重新开始,要么接上去
      curMin = min(x, curMin * x);
      ans = max(ans, curMax);
    }
    return ans;
  }
};
}

单元测试

以下用例都在本仓库里实际编译运行过,图解里的数据也取自这里。

TEST q152_maximum_product_subarray13 行
lc0152::Solution s;
vector<int> a{2, 3, -2, 4};
CHECK_EQ(s.maxProduct(a), 6);
vector<int> b{-2, 0, -1};
CHECK_EQ(s.maxProduct(b), 0);
vector<int> c{-2};  // 单元素负数,考验初值
CHECK_EQ(s.maxProduct(c), -2);
vector<int> d{-2, 3, -4};
CHECK_EQ(s.maxProduct(d), 24);  // 负负得正
vector<int> e{2, -5, -2, -4, 3};
CHECK_EQ(s.maxProduct(e), 24);
vector<int> f{-4, -3, -2};  // 只有前两个负数能配对:(-4)×(-3)=12;三个一起乘变 -24
CHECK_EQ(s.maxProduct(f), 12);

↑↓ 选择↵ 打开/ 随时唤起