2021/3/29 乘积最大子数组

题目描述

描述转载自力扣《152. 乘积最大子数组》
给你一个整数数组 nums ，请你找出数组中乘积最大的连续子数组（该子数组中至少包含一个数字），并返回该子数组所对应的乘积。

示例1

输入: [2,3,-2,4]
输出: 6
解释: 子数组 [2,3] 有最大乘积 6。

示例2

输入: [-2,0,-1]
输出: 0
解释: 结果不能为 2, 因为 [-2,-1] 不是子数组。

解题思路

1. 完成这题之前，建议先完成牛客《子数组的最大累加和问题》 或 力扣《最大子序和》。本题是基于上面给出的题目变型的。如果已经做过并理解这道题的解法，可以直接跳到第 3 条。
2. 在我们完成牛客《子数组的最大累加和问题》 或 力扣《最大子序和》后，我们得知，这类属于单串问题的题目可以用每次规模减少 1 来拆分子问题，像最大子序和，我们可以拆分子问题为：“在 范围内，以 结尾的最大子序和，且当 ” 。我们根据这个描述，得出最大子序和问题的状态转移方程
3. 我们尝试借用求最大子序和问题的状态转移方程来解决现在这个问题，得状态转移方程 。可以发现，我们并不能直接使用上一个状态的最优解得出最新状态的最优解。比如有一个数组 [-1, 2, -2]，我们用这个状态转移方程最终只能得出结果 2，但实际上结果是
4. 实际上，本问题最大的阻碍在于负号，但我们可以把符号看作“最大的负数”，也就是最小数。我们维护两个数组，一个用来记录最大乘积 max，另一个记录最小乘积 min。当遍历到的 是负数，min 也是负数时，它们相乘就会得到最大值，赋值给 max。我们可以求出这个状态转移方程为
   

Java代码实现

1. 普通版

class Solution {
    public int maxProduct(int[] nums) {
        int[] max = Arrays.copyOf(nums, nums.length);
        int[] min = Arrays.copyOf(nums, nums.length);
        int res = nums[0];
        for (int i = 1; i < nums.length; ++i) {
            max[i] = Math.max(nums[i], Math.max(nums[i] * max[i - 1], nums[i] * min[i - 1]));
            min[i] = Math.min(nums[i], Math.min(nums[i] * max[i - 1], nums[i] * min[i - 1]));
            res = Math.max(res, max[i]);
        }
        return res;
    }
}

2. 滚动数组版

class Solution {
    public int maxProduct(int[] nums) {
        int max = nums[0], min = nums[0];
        int res = nums[0];
        for (int i = 1; i < nums.length; ++i) {
            int m = max, n = min;
            max = Math.max(nums[i], Math.max(nums[i] * m, nums[i] * n));
            min = Math.min(nums[i], Math.min(nums[i] * m, nums[i] * n));
            res = Math.max(res, max);
        }
        return res;
    }
}