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

请注意，一个只包含一个元素的数组的乘积是这个元素的值。

示例 1:

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

示例 2:

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

解题思路

这道题的坑点在于 当前位置的最优解未必是由前一个位置的最优解转移得到的。

例如，[5,6,-3,4,-3] ，如果我们状态转移以为是只跟前一个元素有关，那就错了，因为负数的存在，使得当两个负数（不一定连续在一起）相乘，会得到正数！所以除了维护最大值，还要维护最小值，以备在遇到下一个负数时“逆风翻盘”。

• 定义状态：数组 nums[i] ， max[i] 是最大乘积，min[i] 是最小乘积
• 基础情况：dp[0] = nums[0] （nums[0] 只包含一个元素，乘积是这个元素的值）
• 状态转移： nums[i] 要么跟前面的最大最小相乘，要么不相乘“自立门户”
  • max[i] = max(currMax * nums[i], nums[i])
  • min[i] = min(currMin * nums[i], nums[i])
  • 核心点：当负数出现时则 currMax 与 currMin 进行交换再进行下一步计算

---

Java 实现

    public int maxProduct(int[] nums) {
        int min = nums[0];
        int max = nums[0];
        int result = nums[0];
        for (int i = 1; i < nums.length; i++){
            int curr = nums[i];
            if (curr < 0){
                int temp = min;
                min = max;
                max = temp;
            }
            min = Math.min(curr, curr * min);
            max = Math.max(curr, curr * max);
            if (max > result){
                result = max;
            }
        }
        return result;
    }