题目描述:
给你一个整数数组,在该数组的所有子数组中,找到一个子数组中所有元素相乘积最大,返回这个最大的积。子数组就是一个数组中,由一个或几个下标连续的元素,组成的小数组,就叫原数组的子数组。
思路:
这一题和题目:53. 最大子数组和很像。但是又复杂了一点。所以建议先搞懂53题,再来看这道题。在53题曾经说过求子数组问题,都可以向一种思维上靠拢。即以某一个元素为结尾的子数组中,得到一个结果。然后以每一个元素都作为结尾,得到很多个结果,然后在这些结果中进行比较,一定得到正确的结果。
而本题和加法又不太一样,加法比如说想找到以每一个元素为结尾的子数组的最大和,只需要前一个元素为结尾的子数组最大和能拿到,就可以得到该元素为结尾的子数组的最大和。
举个例子:加法中,数组为nums
,想要得到下标i
为结尾的子数组的最大和X
,只需要得到下标i-1
为结尾的子数组的最大和Y
,然后选择要不要加上nums[i]
就可以得到了。即 X = Math.max(nums[i], Y + nums[i])
。即最大值只会出现在nums[i]
和Y + nums[i]
中选择。
但是乘法不一样,乘法会有负负得正。乘积最大值,不仅会出现在nums[i]
、Y * nums[i]
中。如果nums[i]
是负值,下标i-1
为结尾的子数组的最小乘积M
,nums[i] * M
也可能是乘积最大值。
举个例子:[100, 6, -2, -3]
,以-3
结尾的子数组的最大乘积就是-3 * -1200(以-2为结尾的子数组的最小乘积) = 3600
。
所以,乘积需要得到两个结果,以某一下标结尾的子数组中最大乘积以及最小乘积。
步骤:
1、初始化动态规划数组,以0
下标结尾的子数组最大乘积、最小乘积都是nums[0]
本身
2、在循环中,通过i - 1
的最大乘积和最小乘积,结合公式,得到三条数据,三者进行比较,得到i
的最大乘积和最小乘积,更新dp
数组,以及判断最大乘积是否需要更新
3、循环结束后,返回最大乘积
代码:
未优化空间的动态规划版本
public int maxProduct(int[] nums) {
int n = nums.length;
int[] dpMax = new int[n];
int[] dpMin = new int[n];
// 记录以 0 为结尾的子数组的最大累乘积和最小累乘积
dpMax[0] = nums[0];
dpMin[0] = nums[0];
int ans = nums[0];
for (int i = 1; i < nums.length; i++) {
// 记录三种可能性
int p1 = nums[i];
int p2 = nums[i] * dpMax[i - 1];
int p3 = nums[i] * dpMin[i - 1];
// 从三种可能性中取最大累乘积和最小累乘积
int curMax = Math.max(p1, Math.max(p2, p3));
int curMin = Math.min(p1, Math.min(p2, p3));
// 将最大累乘积与ans比较
ans = Math.max(ans, curMax);
// 更新以 i 为结尾的子数组的最大累乘积和最小累乘积
dpMax[i] = curMax;
dpMin[i] = curMin;
}
return ans;
}
空间优化代码
// 因为dp[i]只和dp[i - 1]有关,所以可以优化空间
public int maxProduct(int[] nums) {
// 记录以 0 为结尾的子数组的最大累乘积
int preMax = nums[0];
// 记录以 0 为结尾的子数组的最小累乘积
int preMin = nums[0];
int ans = nums[0];
for (int i = 1; i < nums.length; i++) {
// 记录三种可能性
int p1 = nums[i];
int p2 = nums[i] * preMax;
int p3 = nums[i] * preMin;
// 从三种可能性中取最大累乘积和最小累乘积
int curMax = Math.max(p1, Math.max(p2, p3));
int curMin = Math.min(p1, Math.min(p2, p3));
// 将最大累乘积与ans比较
ans = Math.max(ans, curMax);
// 更新以 i 为结尾的子数组的最大累乘积和最小累乘积
preMax = curMax;
preMin = curMin;
}
return ans;
}