LeetCode 152. 乘积最大子数组

Categories:

Tags:

题目描述
思路分析
1. 解法一：双状态动态规划（推荐）
2. 解法二：前后双向遍历
相似题目

题目描述

✅ 152. 乘积最大子数组

思路分析

解法一：双状态动态规划（推荐）

核心思路：

与「最大子数组和」（53 题）不同，乘积中负数会让”最大变最小、最小变最大”，因此需要同时追踪以当前元素结尾的最大乘积和最小乘积

状态定义：curMax 为以 nums[i] 结尾的最大乘积，curMin 为以 nums[i] 结尾的最小乘积

转移逻辑：若 nums[i] < 0，乘以负数后最大变最小、最小变最大，先交换 curMax 与 curMin，再分别更新

curMax = max(nums[i], curMax * nums[i])，curMin = min(nums[i], curMin * nums[i])

每轮用 curMax 更新全局答案

为什么需要 curMin：若后续遇到负数，当前最小乘积（负数）乘以负数后可能成为最大值

复杂度分析：

时间复杂度：O(n)，其中 n 为数组长度，只需一次线性遍历

空间复杂度：O(1)，只使用常数级变量

class Solution {
    public int maxProduct(int[] nums) {
        int maxP = nums[0], minP = nums[0];
        int res = nums[0];

        for (int i = 1; i < nums.length; i++) {
            // 遇到负数时，最大值和最小值互换
            if (nums[i] < 0) {
                int temp = maxP;
                maxP = minP;
                minP = temp;
            }
            // 要么从当前元素重新开始，要么继续扩展之前的子数组
            maxP = Math.max(nums[i], maxP * nums[i]);
            minP = Math.min(nums[i], minP * nums[i]);
            res = Math.max(res, maxP);
        }
        return res;
    }
}

func maxProduct(nums []int) int {
	curMax, curMin := nums[0], nums[0]
	res := nums[0]

	for i := 1; i < len(nums); i++ {
		// 遇到负数时，最大值和最小值互换
		if nums[i] < 0 {
			curMax, curMin = curMin, curMax
		}
		// 要么从当前元素重新开始，要么继续扩展之前的子数组
		curMax = max(nums[i], curMax*nums[i])
		curMin = min(nums[i], curMin*nums[i])
		res = max(res, curMax)
	}

	return res
}

解法二：前后双向遍历

核心思路：

若数组中负数个数为偶数，整个数组乘积就是最大值；奇数个负数时，答案在去掉最左侧或最右侧负数后的子数组中

从左到右、从右到左各遍历一次，维护前缀乘积，遇到 0 就重置为 1，取两次遍历中的最大值

两次遍历覆盖了所有以某一端点结尾的子数组乘积，无需处理负数交换逻辑

复杂度分析：

时间复杂度：O(n)，其中 n 为数组长度，正反各遍历一次

空间复杂度：O(1)，只使用常数级变量

class Solution {
    public int maxProduct(int[] nums) {
        int n = nums.length;
        int res = nums[0];
        int cur = 1;

        // 从左到右遍历，维护前缀乘积
        for (int i = 0; i < n; i++) {
            if (cur == 0) {
                cur = 1;
            }
            cur *= nums[i];
            res = Math.max(res, cur);
        }

        cur = 1;
        // 从右到左遍历，维护后缀乘积
        for (int i = n - 1; i >= 0; i--) {
            if (cur == 0) {
                cur = 1;
            }
            cur *= nums[i];
            res = Math.max(res, cur);
        }

        return res;
    }
}

func maxProduct(nums []int) int {
	n := len(nums)
	res := nums[0]
	cur := 1

	// 从左到右遍历，维护前缀乘积
	for i := 0; i < n; i++ {
		if cur == 0 {
			cur = 1
		}
		cur *= nums[i]
		res = max(res, cur)
	}

	cur = 1
	// 从右到左遍历，维护后缀乘积
	for i := n - 1; i >= 0; i-- {
		if cur == 0 {
			cur = 1
		}
		cur *= nums[i]
		res = max(res, cur)
	}

	return res
}

相似题目

题目	难度	考察点
53. 最大子数组和	中等	动态规划/贪心子数组
198. 打家劫舍	中等	DP 维护两个状态
238. 除自身以外数组的乘积	中等	前缀积+后缀积
628. 三个数的最大乘积	简单	排序/贪心
713. 乘积小于 K 的子数组	中等	滑动窗口乘积
42. 接雨水	困难	DP 维护左右最值

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2026/75102165