152 乘积最大子数组
一、题目
给你一个整数数组 nums ，请你找出数组中乘积最大的非空连续 子数组（该子数组中至少包含一个数字），并返回该子数组所对应的乘积。
测试用例的答案是一个 32-位 整数。
请注意，一个只包含一个元素的数组的乘积是这个元素的值。
二、题解
方法一：动态规划
思路：动态规划。
1. 核心思路
本题要求的是连续子数组的最大乘积。
由于数组中可能出现负数，因此只记录最大乘积是不够的。
原因是：
- 正数乘以最大乘积，仍然可能得到最大乘积；
- 负数乘以最大乘积，可能变成最小乘积；
- 负数乘以最小乘积，反而可能变成最大乘积。
例如：
nums = [-2, 3, -4]遍历到 -4 时，前面的最小乘积为：
-2 × 3 = -6此时：
-6 × -4 = 24最小乘积乘以负数，反而得到了最大乘积。
因此，需要同时维护两个动态规划数组：
maxDp[i]：以nums[i]结尾的连续子数组的最大乘积；minDp[i]：以nums[i]结尾的连续子数组的最小乘积。
对于当前位置 i，有三种选择：
- 只选择当前数字
nums[i]； - 将当前数字接在之前最大乘积子数组的后面；
- 将当前数字接在之前最小乘积子数组的后面。
状态转移公式为：
maxDp[i] = max(
nums[i],
maxDp[i - 1] × nums[i],
minDp[i - 1] × nums[i]
)
minDp[i] = min(
nums[i],
maxDp[i - 1] × nums[i],
minDp[i - 1] × nums[i]
)最终答案是所有 maxDp[i] 中的最大值。
2. 具体步骤
- 创建两个长度为
n的数组maxDp和minDp。 - 初始化
maxDp[0]和minDp[0]为nums[0]。 - 从下标
1开始遍历数组。 - 计算以当前位置结尾的最大乘积和最小乘积。
- 使用
result记录遍历过程中出现的最大乘积。 - 遍历结束后返回
result。
3. 关键逻辑
int current = nums[i];
maxDp[i] = Math.max(
current,
Math.max(
maxDp[i - 1] * current,
minDp[i - 1] * current
)
);
minDp[i] = Math.min(
current,
Math.min(
maxDp[i - 1] * current,
minDp[i - 1] * current
)
);解释：
对于以 nums[i] 结尾的连续子数组，最大乘积可能来自三种情况：
1. nums[i]
2. maxDp[i - 1] × nums[i]
3. minDp[i - 1] × nums[i]为什么需要考虑只选择当前数字？
例如：
nums = [-2, 3]遍历到 3 时：
-2 × 3 = -6此时继续之前的子数组不是最优选择，应该从当前数字 3 重新开始。
因此，需要将 nums[i] 本身也加入比较。
4. 代码
class Solution {
public int maxProduct(int[] nums) {
int n = nums.length;
// maxDp[i]：以 nums[i] 结尾的连续子数组的最大乘积
int[] maxDp = new int[n];
// minDp[i]：以 nums[i] 结尾的连续子数组的最小乘积
int[] minDp = new int[n];
// 初始化第一个位置
maxDp[0] = nums[0];
minDp[0] = nums[0];
// 记录整个数组中的最大乘积
int result = nums[0];
for (int i = 1; i < n; i++) {
int current = nums[i];
// 当前最大乘积有三种来源：
// 1. 只选择当前数字
// 2. 之前的最大乘积乘以当前数字
// 3. 之前的最小乘积乘以当前数字
maxDp[i] = Math.max(
current,
Math.max(
maxDp[i - 1] * current,
minDp[i - 1] * current
)
);
// 当前最小乘积同样有三种来源
minDp[i] = Math.min(
current,
Math.min(
maxDp[i - 1] * current,
minDp[i - 1] * current
)
);
// 更新最终答案
result = Math.max(result, maxDp[i]);
}
return result;
}
}5. 复杂度分析
时间复杂度：
说明：只需要遍历数组一次，每个位置的计算都是常数时间。
空间复杂度：
说明：使用了两个长度为 n 的动态规划数组。
方法二：动态规划空间优化
思路：动态规划优化。
1. 核心思路
方法一中：
maxDp[i]只依赖：
maxDp[i - 1]而：
minDp[i]也只依赖：
minDp[i - 1]因此，没有必要保存完整的动态规划数组，只需要使用两个变量保存上一个位置的最大乘积和最小乘积。
定义：
maxProduct：以当前位置结尾的最大乘积
minProduct：以当前位置结尾的最小乘积
result：整个数组中的最大乘积当当前数字为负数时：
最大乘积 × 负数可能变成最小乘积，而：
最小乘积 × 负数可能变成最大乘积。
因此，可以先交换 maxProduct 和 minProduct，再进行状态更新。
2. 具体步骤
- 使用数组第一个元素初始化
maxProduct、minProduct和result。 - 从数组第二个元素开始遍历。
- 如果当前数字是负数，交换
maxProduct和minProduct。 - 更新以当前位置结尾的最大乘积。
- 更新以当前位置结尾的最小乘积。
- 使用
result记录遍历过程中出现的最大乘积。 - 遍历结束后返回
result。
3. 关键逻辑
if (current < 0) {
int temp = maxProduct;
maxProduct = minProduct;
minProduct = temp;
}
maxProduct = Math.max(current, maxProduct * current);
minProduct = Math.min(current, minProduct * current);解释：
如果 current 是负数，那么乘法之后，最大值和最小值的作用会互换。
例如：
maxProduct = 6
minProduct = -3
current = -4计算结果为：
6 × -4 = -24
-3 × -4 = 12原来的最大乘积得到了更小的结果，而原来的最小乘积反而得到了更大的结果。
所以，当当前数字为负数时，可以先交换：
maxProduct 和 minProduct交换之后再计算：
maxProduct = Math.max(current, maxProduct * current);
minProduct = Math.min(current, minProduct * current);其中：
maxProduct * current表示将当前数字接到之前的连续子数组后面。
而：
current表示放弃之前的连续子数组，从当前数字重新开始。
4. 代码
class Solution {
public int maxProduct(int[] nums) {
// 以当前位置结尾的最大乘积
int maxProduct = nums[0];
// 以当前位置结尾的最小乘积
int minProduct = nums[0];
// 整个数组中的最大乘积
int result = nums[0];
for (int i = 1; i < nums.length; i++) {
int current = nums[i];
// 当前数字为负数时：
// 最大乘积和最小乘积乘以负数后会互换作用
if (current < 0) {
int temp = maxProduct;
maxProduct = minProduct;
minProduct = temp;
}
// 要么只选择当前数字，
// 要么将当前数字接在之前的连续子数组后面
maxProduct = Math.max(current, maxProduct * current);
minProduct = Math.min(current, minProduct * current);
// 更新整个数组的最大乘积
result = Math.max(result, maxProduct);
}
return result;
}
}5. 复杂度分析
时间复杂度：
说明：只需要遍历数组一次，每次循环只进行常数次计算。
空间复杂度：
说明：只使用了 maxProduct、minProduct 和 result 等常数个变量。
评论