152 乘积最大子数组

本文最后更新于：2021年7月28日 晚上

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

示例 1:

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

示例 2:

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

Solution

  • 动态规划
  • dp[i] [2]： 以 nums[i] 结尾的子数组，dp[i] [0] 表示最小值，dp[i] [1] 表示最大值。
  • 递推公式

if nums[i] >= 0 :

dp[i][0] = min(nums[i], nums[i] * dp[i - 1][0])
dp[i][1] = max(nums[i], nums[i] * dp[i - 1][1])

if nums[i] < 0 :

dp[i][0] = min(nums[i], nums[i] * dp[i - 1][1])
dp[i][1] = max(nums[i], nums[i] * dp[i - 1][0])

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    int maxProduct(vector<int>& nums) {
        int n = nums.size();
        if (n == 0) return 0;
        vector<vector<int>> dp(n, vector<int>(2, 0));   // 以 nums[i] 结尾的乘积最大子数组
        dp[0][0] = nums[0], dp[0][1] = nums[0];
        for (int i = 1; i < n; ++i) {
            if (nums[i] >= 0) {
                dp[i][0] = min(nums[i], nums[i] * dp[i-1][0]);
                dp[i][1] = max(nums[i], nums[i] * dp[i-1][1]);
            } else {
                dp[i][0] = min(nums[i], nums[i] * dp[i-1][1]);
                dp[i][1] = max(nums[i], nums[i] * dp[i-1][0]);
            }
        }
        int res = dp[0][1];
        for (int i = 1; i < n; ++i) {
            res = max(res, dp[i][1]);
        }
        return res;
    }
};
algo leetcode 动态规划

本博客所有文章除特别声明外，均采用 CC BY-SA 4.0 协议 ，转载请注明出处！