LeetCode-152. 乘积最大子数组
题目来源
152. 乘积最大子数组
题目详情
给你一个整数数组 nums ，请你找出数组中乘积最大的连续子数组（该子数组中至少包含一个数字），并返回该子数组所对应的乘积。
示例 1:
输入: [2,3,-2,4]
输出: 6
解释: 子数组 [2,3] 有最大乘积 6。
示例 2:
输入: [-2,0,-1]
输出: 0
解释: 结果不能为 2, 因为 [-2,-1] 不是子数组。
题解分析
解法一-动态规划
- 这题其实是最大连续子数组题目的变型，原来的题目是求解连续子数组的最大和。但遗憾的是，这题和原来的题目还是有很大区别的。因为乘积时可能遇到负数，但是负数和负数相乘会导致正数的出现，这是加法和减法所没有的特征。
- 因此，也不能使用类似于最大连续子数组和的状态转移方程（\(dp[i] = max(dp[i-1] + nums[i], nums[i]\)，最大值为dp结果数组中各元素的最大值），需要采用新的思路来求解乘积子数组的最大值。
- 考虑到这里有负数会影响状态转移，并且如果当前数为负数，则我们希望该数前面的乘积为负数，且越小越好；如果当前数为正数，则我们希望前面数的乘积为正，且越大越好。
- 我们可以定义两个dp数组，一个存储最大乘积，一个存储最小乘积，结果为最大乘积数组各元素中的最大值。
class Solution {
final int MINS = -0X3F3F3F3F;
public int maxProduct(int[] nums) {
if(nums == null || nums.length == 0){
return 0;
}
int len = nums.length;
int[] dpmax = Arrays.copyOf(nums, len);
int[] dpmin = Arrays.copyOf(nums, len);
for(int i=1; i解法二-滚动数组压缩
- 从上一个解法可以看到，不管是dpmax，还是dpmin数组，它们的状态只依赖于上一次的状态，所以我们可以将这些一维数组进行压缩，这可以各使用一个变量来记录最大和最小。
- 需要注意的是，结果并不是最终的dpmax变量，而是在每次遍历过程中计算的最大值。所以，在每次循环期间，需要计算一个最大值。
class Solution {
final int MINS = -0X3F3F3F3F;
public int maxProduct(int[] nums) {
if(nums == null || nums.length == 0){
return 0;
}
int len = nums.length;
int maxs = nums[0], mins = nums[0];
int res = nums[0];
for(int i=1; i