乘积最大子数组

给你一个整数数组 nums ，请你找出数组中乘积最大的非空连续

子数组

（该子数组中至少包含一个数字），并返回该子数组所对应的乘积。

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

示例 1:

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

示例 2:

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

提示:

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

如果数组中都是正数问题很简单,f[i]表示以nums[i]结尾的子数组乘积最大值,f[i]=Math.max(nums[i],f[i-1]*nums[i])

但是数组中既包括正数又包括负数，这种做法并不满足最优子结构，如果nums={5,6,−3,4,−3},f={5,6,−3,4,−3},这样得到的答案是6，但显然答案等于全部数的乘积。

考虑当前位置的正负性：

  • 如果当前位置是正数，那么最大值的状态转移方程同上
  • 如果当前位置是负数，最大值应该是负数乘以一个最小的负数

所以应该同时维护乘积的最大值和最小值，每次更新最大值和最小值时，需要比较nums[i],nums[i]*max,nums[i]*min这三个数的大小关系。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public int maxProduct(int[] nums) {
        int n = nums.length;
        int max = nums[0];
        int min = max;
        int result = max;
        for (int i = 1; i < n; i++) {
            int t = max;
            max = Math.max(nums[i], Math.max(max * nums[i], min * nums[i]));
            min = Math.min(nums[i], Math.min(t * nums[i], min * nums[i]));
            result = Math.max(result, max);
        }
        return result;
    }
}