题解

题面描述

给定一个整数数组 $nums$，要求找出数组中乘积最大的非空连续子数组，并返回该子数组所对应的乘积。注意：子数组要求在数组中是连续的一段。测试用例的答案保证为 $32$-位整数。

思路解析

由于数组中既可能有正数也可能有负数，负数相乘会使得结果变正，同时遇到 $0$ 时会将乘积清零，因此我们需要同时记录当前子数组的最大值和最小值。具体思路如下：

• 定义 $dp_{max}[i]$ 表示以下标 $i$ 结尾的子数组所能获得的最大乘积；
• 定义 $dp_{min}[i]$ 表示以下标 $i$ 结尾的子数组所能获得的最小乘积；
• 当遇到负数时，由于负负得正，当前最大值可能由之前的最小值乘以当前值得到；
• 状态转移公式为
  • $dp_{max}[i]$ = max($nums[i]$, $dp_{max}[i-1]$ * $nums[i]$, $dp_{min}[i-1]$ * $nums[i]$)
  • $dp_{min}[i]$ = min($nums[i]$, $dp_{max}[i-1]$ * $nums[i]$, $dp_{min}[i-1]$ * $nums[i]$)
• 同时维护全局最大值即可。

代码分析

1. 动态规划思想：
   利用两个变量记录当前最大和最小乘积，通过遍历数组不断更新状态。时间复杂度为 $O(n)$，空间复杂度可以做到 $O(1)$。

2. 负数与 $0$ 的特殊处理：
   当遇到负数时，交换当前的最大和最小值；当遇到 $0$ 时，重新初始化最大和最小值为 $0$ 或当前数。

3. 边界条件：
   初始状态设定为数组的第一个元素，保证子数组非空。

C++

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

class Solution {
public:
    // 返回数组中乘积最大的连续子数组乘积
    int maxProduct(vector<int>& nums) {
        // 初始化最大值、最小值以及结果
        int curMax = nums[0], curMin = nums[0], res = nums[0];
        for (size_t i = 1; i < nums.size(); i++) {
            // 当遇到负数时，交换最大值和最小值
            if(nums[i] < 0)
                swap(curMax, curMin);
            // 更新当前最大值和最小值
            curMax = max(nums[i], curMax * nums[i]); // 当前最大值 = max(当前数, 前面的最大乘积乘以当前数)
            curMin = min(nums[i], curMin * nums[i]); // 当前最小值 = min(当前数, 前面的最小乘积乘以当前数)
            // 更新全局最大值
            res = max(res, curMax);
        }
        return res;
    }
};

int main(){
    // 读取输入
    vector<int> nums;
    int x;
    while(cin >> x) { // 以空格或换行分隔输入
        nums.push_back(x);
    }
    // 调用解法
    Solution sol;
    int result = sol.maxProduct(nums);
    // 输出结果
    cout << result;
    return 0;
}

Python

class Solution:
    # 返回数组中乘积最大的连续子数组乘积
    def maxProduct(self, nums: list[int]) -> int:
        # 初始化当前最大值、最小值以及结果
        cur_max = nums[0]
        cur_min = nums[0]
        res = nums[0]
        # 遍历数组
        for num in nums[1:]:
            # 当遇到负数时交换当前最大值和最小值
            if num < 0:
                cur_max, cur_min = cur_min, cur_max
            # 更新当前最大值和最小值
            cur_max = max(num, cur_max * num)  # 当前最大值 = max(当前数, 前面乘积乘以当前数)
            cur_min = min(num, cur_min * num)  # 当前最小值 = min(当前数, 前面乘积乘以当前数)
            # 更新全局最大值
            res = max(res, cur_max)
        return res

if __name__ == "__main__":
    import sys
    # 读取输入：以空格或换行分隔数字
    nums = list(map(int, sys.stdin.read().split()))
    sol = Solution()
    print(sol.maxProduct(nums))

Java

import java.util.Scanner;
import java.util.ArrayList;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        ArrayList<Integer> list = new ArrayList<>();
        // 读取输入：以空格或换行分隔数字
        while (scanner.hasNextInt()) {
            list.add(scanner.nextInt());
        }
        scanner.close();
        int[] nums = new int[list.size()];
        for (int i = 0; i < list.size(); i++) {
            nums[i] = list.get(i);
        }
        Solution sol = new Solution();
        int result = sol.maxProduct(nums);
        System.out.println(result);
    }
}

class Solution {
    // 返回数组中乘积最大的连续子数组乘积
    public int maxProduct(int[] nums) {
        // 初始化当前最大值、最小值以及结果
        int curMax = nums[0], curMin = nums[0], res = nums[0];
        for (int i = 1; i < nums.length; i++) {
            // 当遇到负数时交换当前最大值和最小值
            if (nums[i] < 0) {
                int temp = curMax;
                curMax = curMin;
                curMin = temp;
            }
            // 更新当前最大值和最小值
            curMax = Math.max(nums[i], curMax * nums[i]); // 当前最大值 = max(当前数, 前面乘积乘以当前数)
            curMin = Math.min(nums[i], curMin * nums[i]); // 当前最小值 = min(当前数, 前面乘积乘以当前数)
            // 更新全局最大值
            res = Math.max(res, curMax);
        }
        return res;
    }
}

题目内容

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

测试用例的答案是一个 $32$-位整数。

输入描述

一个整数数组$nums$

输出描述

一个整数表示最大乘积

样例1

输入

2 3 -2 4

输出

6

说明

子数组$[2,3]$有最大乘积$6$。

样例2

输入

-2 0 -1

输出

0

说明

结果不能为 $2$, 因为$[-2,-1]$不是子数组。

提示：

• $1 <= nums.length <= 2 * 10^4$
• $-10 <= nums[i] <= 10$
• $nums$ 的任何子数组的乘积都保证是一个 $32$-位 整数