乘积最大子数组

GitHub跳转原题关系图返回列表

同时维护以当前位置结尾的最大和最小乘积，负数交换两者，取全局最大。

OJ: leetcodecn

题目 ID: maximum-product-subarray

难度:普及+/提高

标签:动态规划

日期: 2026-07-29 12:46

目录

  1. 题意
  2. 思路
  3. 代码
  4. 复杂度
  5. 总结

题意

求数组中乘积最大的连续子数组。

思路

同时维护以当前位置结尾的最大乘积 mx 和最小乘积 mn。遇到负数时 mx 和 mn 交换（因为负数使最大变最小、最小变最大），然后正常更新：mx = max(x, mx*x), mn = min(x, mn*x)。

代码

cpp
#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    int maxProduct(vector<int> &nums) {
        int ans = nums[0], mx = nums[0], mn = nums[0];
        for (int i = 1; i < (int)nums.size(); i++) {
            int x = nums[i];
            int a = max({x, mx * x, mn * x});
            int b = min({x, mx * x, mn * x});
            mx = a;
            mn = b;
            ans = max(ans, mx);
        }
        return ans;
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    vector<int> a(n);
    for (int &x : a)
        cin >> x;
    cout << Solution().maxProduct(a) << '\n';
    return 0;
}
python
#!/usr/bin/env python3
from typing import List


class Solution:
    def maxProduct(self, nums: List[int]) -> int:
        ans = mx = mn = nums[0]
        for x in nums[1:]:
            a = max(x, mx * x, mn * x)
            b = min(x, mx * x, mn * x)
            mx, mn = a, b
            ans = max(ans, mx)
        return ans


def main():
    n = int(input())
    a = list(map(int, input().split()))
    print(Solution().maxProduct(a))


if __name__ == "__main__":
    main()

复杂度

  • 时间复杂度：O(n)O(n)。
  • 空间复杂度：O(1)O(1)。

总结

乘积子数组的关键是负数会交换最大最小贡献，因此必须同时维护两者。这与最大子数组和不同：加法不会翻转符号。