leetcode热题HOT 152. 乘积最大子数组

一、问题描述：

给你一个整数数组 nums ，请你找出数组中乘积最大的非空连续子数组（该子数组中至少包含一个数字），并返回该子数组所对应的乘积。
测试用例的答案是一个 32-位 整数。

二、问题分析：

1. 考虑到乘积的特性，当乘以负数时，最大乘积会变成最小乘积，最小乘积会变成最大乘积。因此，在更新当前位置的最大乘积和最小乘积时，需要考虑前一个位置的最大乘积和最小乘积，并与当前元素相乘，以确保不会错过最大乘积或最小乘积。
2. 具体而言:当前元素 nums[i - 1] 为正数时，最大乘积可以由当前元素与前一个位置的最大乘积（max[i - 1] 为正）相乘得到，同时也可能是当前元素本身（max[i - 1]为负）；最小乘积同理。当前元素 nums[i - 1] 为负数时，最大乘积可以由当前元素与前一个位置的最小乘积（min[i - 1]为负）相乘得到，同时也可能是当前元素本身（min[i - 1] 为正）：
   情况一：nums[i - 1]为负数，min[i - 1]是负数，min[i - 1] * nums[i - 1]为最大的正数。
   情况二：nums[i - 1]为负数，min[i - 1]是正数，nums[i - 1]为最大的正数。
   情况三：nums[i - 1]是正数，max[i - 1]是负数，nums[i - 1]为最大的正数。
   情况四：nums[i - 1]是正数，max[i - 1]是正数，max[i - 1] * nums[i - 1]为最大的正数。
3. 因此，设计两个数组 max 和 min，分别用于跟踪以当前位置结束的连续子数组的最大乘积和最小乘积。然后，在每次迭代中，根据当前元素的正负情况，更新 max[i] 和 min[i]，最终得到数组中连续子数组的最大乘积。

三、代码示例：

class Solution {
    public int maxProduct(int[] nums) {
        int result = Integer.MIN_VALUE;
        int[] max = new int[nums.length + 1];
        int[] min = new int[nums.length + 1];
        min[0] = 1;
        max[0] = 1;
        for(int i = 1; i <= nums.length; i++) {
            //情况一：nums[i - 1]为负数，min[i - 1]是负数，min[i - 1] * nums[i - 1]为最大的正数
            //情况二：nums[i - 1]为负数，min[i - 1]是正数，nums[i - 1]为最大的正数
            //情况三：nums[i - 1]是正数，max[i - 1]是负数，nums[i - 1]为最大的正数
            //情况四：nums[i - 1]是正数，max[i - 1]是正数，max[i - 1] * nums[i - 1]为最大的正数
            max[i] = Math.max(min[i - 1] * nums[i - 1], Math.max(nums[i - 1], max[i - 1] * nums[i - 1]));
            min[i] = Math.min(max[i - 1] * nums[i - 1], Math.min(nums[i - 1], min[i - 1] * nums[i - 1]));
            result = Math.max(result, max[i]);
        }
        return result;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

下面对代码进行分析：

1. 创建了两个长度为 nums.length + 1 的数组 max 和 min，用于存储当前位置之前的最大乘积和最小乘积。
2. 初始时，max[0] 和 min[0] 均为1，用于处理空子数组的情况。
3. 使用一个循环遍历数组 nums，从索引 1 开始。
4. 在每次迭代中，更新 max[i] 和 min[i]：
   max[i] 表示以当前位置结束的连续子数组的最大乘积，它可以由以下三种情况中的最大值得出：
   ①当前元素 nums[i - 1] 乘以前一个位置的最小乘积 min[i - 1]；
   ②当前元素 nums[i - 1] 本身；
   ③当前元素 nums[i - 1] 乘以前一个位置的最大乘积 max[i - 1]。
   min[i] 表示以当前位置结束的连续子数组的最小乘积，它可以由以下三种情况中的最小值得出：
   ①当前元素 nums[i - 1] 乘以前一个位置的最小乘积 min[i - 1]；
   ②当前元素 nums[i - 1] 本身；
   ③当前元素 nums[i - 1] 乘以前一个位置的最大乘积 max[i - 1]。
5. 在每次迭代中，更新 result 为当前最大乘积 max[i] 与之前的最大乘积 result 中的较大值。
6. 最后，返回 result，即为数组中连续子数组的最大乘积。

• 时间复杂度：该算法的时间复杂度为 O(n)，其中 n 为数组 nums 的长度。因为只需遍历一次数组，并在每个位置上执行常数时间的操作。

进一步简化空间复杂度，利用两个int型变量代替数组 max 和 min：

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