leetcode152：乘积最大子数组

题目链接

leetcode

题目描述

给你一个整数数组 nums ，请你找出数组中乘积最大的非空连续子数组（该子数组中至少包含一个数字），并返回该子数组所对应的乘积。
测试用例的答案是一个 32-位 整数。

C++ 代码

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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

/*
    根据正负性进行分类讨论。
    如果当前位置是一个负数，
    那么希望以它前一个位置结尾的这段乘积也是负数（负负得正），尽可能负。
    如果当前位置是一个正数，
    那么希望以它前一个位置结尾的这段乘积也是正数，尽可能地大。

    状态表示：
        f_max[i] 表示以第 i 个元素结尾的子数组的最大乘积。
        f_min[i] 表示以第 i 个元素结尾的子数组的最小乘积。
    状态计算：
        考虑 a[i] 加入第 i-1 个元素结尾的子数组，三者取大。
        f_max[i] = max(nums[i], 
        	max(f_max[i-1]*nums[i], f_min[i-1]*nums[i]))
        f_min[i] = min(nums[i], 
        	min(f_min[i-1]*nums[i], f_max[i-1]*nums[i]));

    时间复杂度：O(n)
        其中 n 是数组的长度。
        遍历一次数组，对每个元素进行常数时间的操作。
    空间复杂度：O(n)
*/
class Solution {
public:
    int maxProduct(vector<int>& nums) {
        int n = nums.size();
        vector<int> f_max(n, 0), f_min(n, 0);
        // 初始化
        f_max[0] = nums[0], f_min[0] = nums[0];

        // 状态计算
        for (int i = 1; i < n; i++) {
            f_max[i] = max(nums[i], max(f_max[i-1]*nums[i], f_min[i-1]*nums[i]));
            f_min[i] = min(nums[i], min(f_min[i-1]*nums[i], f_max[i-1]*nums[i]));
        }

        return *max_element(f_max.begin(), f_max.end());
    }
};

/*
    优化空间
    第 i 个状态只和第 i-1 个状态有关，
    两个变量来维护 i-1 时刻的状态。

    时间复杂度：O(n)
    空间复杂度：O(1)
*/
class Solution_1 {
public:
    int maxProduct(vector<int>& nums) {
        // 初始化
        int res = nums[0], f_max = nums[0], f_min = nums[0];

        // 状态计算
        for (int i = 1; i < nums.size(); i++) {
            int last_max = f_max, last_min = f_min;
            f_max = max(nums[i], max(last_max*nums[i], last_min*nums[i]));
            f_min = min(nums[i], min(last_min*nums[i], last_max*nums[i]));
            res = max(res, f_max);
        }

        return res;
    }
};

// 辅助函数：打印数组
void printArray(const vector<int>& nums) {
    cout << "[";
    for (size_t i = 0; i < nums.size(); i++) {
        cout << nums[i];
        if (i != nums.size() - 1) cout << ",";
    }
    cout << "]";
}

int main() {
    Solution solution;
    vector<vector<int>> nums_cases = {
        {2,3,-2,4},
        {-2,0,-1}
    };

    for (auto& nums : nums_cases) {
        cout << "Input: ";
        printArray(nums);
        cout << endl;
        int result = solution.maxProduct(nums);
        cout << "Output: " << result << endl;
    }

    return 0;
}
#leetcode
leetcode152：乘积最大子数组
https://lcf163.github.io/2024/04/14/leetcode152：乘积最大子数组/
作者
乘风的小站
发布于
2024年4月14日
许可协议