时间轴

2026-03-21

init

题目：

P152 乘积最大子数组

https://leetcode.cn/problems/maximum-product-subarray/description/?envType=study-plan-v2&envId=top-100-liked

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <vector>
#include <algorithm>
using std::vector;

class Solution {
    public:
        int maxProduct(vector<int> &nums)
        {
                int i, n = nums.size();
                int max_val = nums[0];
                // dp[i][0] 表示以nums[i]结尾的 乘积最大的非空连续 子数组
                // dp[i][1] 表示以nums[i]结尾的 乘积最小的非空连续 子数组
                // dp[i][0] = max{ dp[i-1][0] * nums[i],dp[i-1][1] *nums[i] , nums[i]}
                // dp[i][1] = min{ dp[i-1][0] * nums[i],dp[i-1][1] *nums[i] , nums[i]}

                vector<vector<int> > dp(n, vector<int>(2));

                dp[0][0] = nums[0];
                dp[0][1] = nums[0];

                for (i = 1; i < n; i++) {
                        dp[i][0] = std::max(
                                { dp[i - 1][0] * nums[i], dp[i - 1][1] * nums[i], nums[i] });
                        dp[i][1] = std::min(
                                { dp[i - 1][0] * nums[i], dp[i - 1][1] * nums[i], nums[i] });
                        max_val = std::max(max_val, dp[i][0]);
                }
                return max_val;
        }
};