一、问题描述：
给你一个整数数组 nums ，请你找出数组中乘积最大的非空连续子数组（该子数组中至少包含一个数字），并返回该子数组所对应的乘积。
测试用例的答案是一个 32-位 整数。
二、问题分析：
- 考虑到乘积的特性，当乘以负数时，最大乘积会变成最小乘积，最小乘积会变成最大乘积。因此，在更新当前位置的最大乘积和最小乘积时，需要考虑前一个位置的最大乘积和最小乘积，并与当前元素相乘，以确保不会错过最大乘积或最小乘积。
- 具体而言:当前元素 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]为最大的正数。 - 因此，设计两个数组 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;
}
}
下面对代码进行分析：
- 创建了两个长度为 nums.length + 1 的数组 max 和 min，用于存储当前位置之前的最大乘积和最小乘积。
- 初始时，max[0] 和 min[0] 均为1，用于处理空子数组的情况。
- 使用一个循环遍历数组 nums，从索引 1 开始。
- 在每次迭代中，更新 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]。 - 在每次迭代中，更新 result 为当前最大乘积 max[i] 与之前的最大乘积 result 中的较大值。
- 最后，返回 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;
}
}
