152. 乘积最大子数组

📝 题目描述

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

测试说明的答案是一个 32-位整数。 请注意，一个只包含一个元素的数组的乘积就是这个元素的值。

---

📌 示例

示例 1

输入：

nums = [2,3,-2,4]

输出：

6

解释：子数组 [2,3] 有最大乘积 6。

示例 2

输入：

nums = [-2,0,-1]

输出：

0

解释：结果不能为 2，因为 [-2,-1] 不是子数组。

---

🚀 最优解：动态规划（跟踪最大/最小值）

🔍 思路解析

核心难点：乘积的符号会随负数反转，当前的最小值（负的绝对值大）乘以新负数，可能变成最大值。因此需要同时跟踪两个状态：

• max：以当前元素结尾的子数组的最大乘积；
• min：以当前元素结尾的子数组的最小乘积。

状态转移规则：

1. 遍历数组每个元素 num；
2. 临时存储当前 max（避免更新后被覆盖）；
3. 新的 max = 取以下三者的最大值：
   • 当前元素本身（单独作为子数组）；
   • 之前的 max × 当前元素；
   • 之前的 min × 当前元素；
4. 新的 min = 取以下三者的最小值：
   • 当前元素本身；
   • 临时存储的旧 max × 当前元素；
   • 之前的 min × 当前元素；
5. 用新的 max 更新全局最大乘积 ans。

---

✅ 完整代码（Java）

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        // 读取数组长度
        int n = scanner.nextInt();
        int[] nums = new int[n];

        // 读取数组元素
        for (int i = 0; i < n; i++) {
            nums[i] = scanner.nextInt();
        }

        Solution solution = new Solution();
        int result = solution.maxProduct(nums);

        System.out.println(result);

        scanner.close();
    }
}

class Solution {
    public int maxProduct(int[] nums) {
        // 初始化：全局最大乘积为最小整数，max/min初始为1（乘积的单位元）
        int ans = Integer.MIN_VALUE;
        int max = 1, min = 1;

        for (int num : nums) {
            // 临时保存当前max，避免更新后影响min的计算
            int temp = max;
            // 计算新的max：当前元素、max*num、min*num 三者取最大
            max = Math.max(Math.max(max * num, num), min * num);
            // 计算新的min：当前元素、旧max*num、min*num 三者取最小
            min = Math.min(Math.min(temp * num, num), min * num);
            // 更新全局最大乘积
            ans = Math.max(ans, max);
        }
        return ans;
    }
}

---

🧠 通俗易懂解释

可以把问题理解为“坐过山车式的乘积计算”：

• 正数让乘积越来越大，但负数会让乘积“反转”（大的变小、小的变大）；
• 因此不仅要记“当前最大乘积”，还要记“当前最小乘积”（防止遇到负数时错过最大值）。

以示例1 nums = [2,3,-2,4] 为例：

1. 元素2：
   • max = max(1×2, 2, 1×2) = 2；
   • min = min(1×2, 2, 1×2) = 2；
   • ans = 2；
2. 元素3：
   • max = max(2×3, 3, 2×3) = 6；
   • min = min(2×3, 3, 2×3) = 3；
   • ans = 6；
3. 元素-2：
   • max = max(6×(-2), -2, 3×(-2)) = max(-12, -2, -6) = -2；
   • min = min(6×(-2), -2, 3×(-2)) = min(-12, -2, -6) = -12；
   • ans 仍为6；
4. 元素4：
   • max = max(-2×4, 4, -12×4) = max(-8, 4, -48) = 4；
   • min = min(-2×4, 4, -12×4) = min(-8, 4, -48) = -48；
   • ans 仍为6（最终结果）。

---

⏱ 时间复杂度

O(n)

只需遍历数组一次，每个元素的计算是常数时间。

---

💾 空间复杂度

O(1)

仅使用了固定数量的变量（ans、max、min、temp），无额外空间消耗。