题目
给你一个整数数组 nums ，请你找出数组中乘积最大的连续子数组（该子数组中至少包含一个数字），并返回该子数组所对应的乘积。
示例
示例1
输入: [2,3,-2,4]
输出: 6
解释: 子数组 [2,3] 有最大乘积 6。
示例2
输入: [-2,0,-1]
输出: 0
解释: 结果不能为 2, 因为 [-2,-1] 不是子数组。
分析
暴力解法：
2层循环，第一层：记录从谁开始算，第二层：从开始往后累乘并记录该层最大值。最后再比较出每层最大值的最大值。
时间复杂度: O(n * n)
代码如下：
private int maxProductByBL(int[] nums) {
int length = nums.length;
if(length ==1){
return nums[0];
}
int max = nums[0];
for (int i = 0; i < length; i++) {
int levelMax = nums[i];
int temp = nums[i];
for (int j = i+1; j < length; j++) {
temp *= nums[j];
if(temp>levelMax){
levelMax = temp;
}
}
if(levelMax>max){
max = levelMax;
}
}
return max;
}
动态规划DP：
定义状态： dp[i][j] 为第i个元素时（乘积必须包含nums[i]元素）的最大子乘积值（j=1）和最小子乘积值（j=0）。包含的意思为，有 {-1 -2 -3} 当i=2时，子乘积包含 {-1 -2 -3} 或者 {-2 -3} 或者 {-3}
定义2个数组的原因：可能会出现负负得正的情况，即-10 * -2 =20，需要去记录一个最大值和一个最小值
状态方程：
nums[i]<=0：小于等于0时
//最小值为：当前元素本值或者前一个最大值乘本值 中最小的
dp[i][0] = Math.min(nums[i],dp[i-1][1] * nums[i]);
//最大值为：当前元素本值或者前一个最小值乘本值 中最大的
dp[i][1] = Math.max(nums[i],dp[i-1][0] * nums[i]);
nums[i]>0：大于0时
//最小值为：当前元素本值或者前一个最小值乘本值 中最小的
dp[i][0] = Math.min(nums[i],dp[i-1][0] * nums[i]);
//最大值为：当前元素本值或者前一个最大值乘本值 中最大的
dp[i][1] = Math.max(nums[i],dp[i-1][1] * nums[i]);
初始状态：
dp[0][0] = num[0]
dp[0][1] = num[0]
返回：
max{dp[i][1]}
时间复杂度: O(n)
空间复杂度: O(n)
代码如下
int length = nums.length;
if(length ==1){
return nums[0];
}
int [][]dp = new int[length][2];
dp[0][0] = nums[0];
dp[0][1] = nums[0];
int max = dp[0][1];
for (int i = 1; i <length ; i++) {
if(nums[i]<=0){
dp[i][0] = Math.min(nums[i],dp[i-1][1] * nums[i]);
dp[i][1] = Math.max(nums[i],dp[i-1][0] * nums[i]);
}else{
dp[i][0] = Math.min(nums[i],dp[i-1][0] * nums[i]);
dp[i][1] = Math.max(nums[i],dp[i-1][1] * nums[i]);
}
if(dp[i][1]>max){
max = dp[i][1];
}
}
return max;
动态规划upgrade
状态、方程、初始、返回 都一样。但是上一个解法的空间复杂度为O(n)，通过观察，其实在遍历的过程中，只需要记录上一个的最大值和最小值即可，然后最大值也在max中保存，所以使用滚动数组的方法，将空间复杂度将为O(1)。
代码如下：
private int maxProductByDP1(int[] nums) {
int length = nums.length;
if(length ==1){
return nums[0];
}
int [][]dp = new int[2][2];
dp[0][0] = nums[0];
dp[0][1] = nums[0];
int max = dp[0][1];
for (int i = 1; i <length ; i++) {
//滚动数组，如果m=1那么n=0，如果m=0那么n=1
int m = i%2;
int n = m == 0 ? 1 : 0;
if(nums[i]<=0){
dp[m][0] = Math.min(nums[i],dp[n][1] * nums[i]);
dp[m][1] = Math.max(nums[i],dp[n][0] * nums[i]);
}else{
dp[m][0] = Math.min(nums[i],dp[n][0] * nums[i]);
dp[m][1] = Math.max(nums[i],dp[n][1] * nums[i]);
}
if(dp[m][1]>max){
max = dp[m][1];
}
}
return max;
}
