152. 乘积最大子数组

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

示例 1:

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

示例 2:

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

通过次数190,778 提交次数452,585

思路

本题与最大自序和类似，若都是正数，则可直接得到状态转移方程dp[i] = max(dp[i - 1] * dp[i],dp[i]),
但本题中会有负数和0的出现，当遇到负数时，遍历得到的最大值将变为最小值，所以计算最大值的同时计算最小值，当遇到负数时将两者交换，即可得到最大值。

Java代码

class Solution {
    public int maxProduct(int[] nums) {
        if (nums.length == 1) {
            return nums[0];
        }
        int maxValue = nums[0];
        int minValue = nums[0];
        int res = nums[0];
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] < 0) {
                int tmp = maxValue;
                maxValue = minValue;
                minValue = tmp;
            }
            if (nums[i] == 0) {
                maxValue = 0;
                minValue = 0;
            }

            maxValue = Math.max(maxValue * nums[i], nums[i]);

            minValue = Math.min(minValue * nums[i], nums[i]);

            res = Math.max(maxValue,res);

        }
        return res;
    }
}