【Leetcode】152.乘积最大子数组

152.乘积最大子数组

题目

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

 

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

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

方法（动态规划）

因为数组中的数可负可正。由于存在负数，那么最大积可能乘以下一个数就变成最小积，最小积可能乘以下一个数就变成最大积。因此我们同时维护两个dp数组：maxDP和minDP。

  • max[i]记录以数组nums中第i个元素结尾的子数组的最大积
  • min[i]记录以数组nums中第i个元素结尾的子数组的最小积

状态转移方程：

  • $maxDP[i] = Max(maxDP[i-1]*nums[i], nums[i], minDP[i-1]*nums[i])$
  • $minDP[i] = Min(minDP[i-1]*nums[i], nums[i], maxDP[i-1]*nums[i])$

特殊情况：若nums[i]为0，则以nums[i]结尾的子数组的乘积只能为0（因为子数组中包括0），于是maxDP[i]和minDP[i]均为0

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public int maxProduct(int[] nums) {
    int res = nums[0];
    int[] maxDP = new int[nums.length];
    int[] minDP = new int[nums.length];
    //base case
    maxDP[0] = nums[0];
    minDP[0] = nums[0];
    for(int i = 1; i < nums.length; i++){
        maxDP[i] = Math.max(maxDP[i-1] * nums[i], Math.max(nums[i], minDP[i-1] * nums[i]));
        minDP[i] = Math.min(minDP[i-1] * nums[i], Math.min(nums[i], maxDP[i-1] * nums[i]));
        res = Math.max(res, maxDP[i]);
    }
    return res;
}
  • 时间复杂度：O(n)
  • 空间复杂度：O(n)

空间优化
i位置上的状态(maxDP和minDP)只与i-1位置上的状态有关，所以更新 maxDP[i]的时候，我们只用到maxDP[i-1]的信息，再之前的信息就用不到了。所以我们不需要维护两个数组，只需要维护两个变量来记录i-1处的位置即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public int maxProduct(int[] nums) {
    int res = nums[0];
    //base case
    int maxDP = nums[0];
    int minDP = nums[0];
    for(int i = 1; i < nums.length; i++){
        //因为在更新minDP前需要更新maxDP，因此需要把前一步的maxDP先保存起来
        int preMax = maxDP;
        maxDP = Math.max(maxDP * nums[i], Math.max(nums[i], minDP * nums[i]));
        minDP = Math.min(minDP * nums[i], Math.min(nums[i], preMax * nums[i]));
        res = Math.max(res, maxDP);
    }
    return res;
}
  • 时间复杂度：O(n)
  • 空间复杂度：O(1)