乘积最大子序列
给定一个整数数组 nums ，找出一个序列中乘积最大的连续子序列（该序列至少包含一个数）。
示例 1:
输入: [2,3,-2,4]
输出: 6
解释: 子数组 [2,3] 有最大乘积 6。
示例 2:
输入: [-2,0,-1]
输出: 0
解释: 结果不能为 2, 因为 [-2,-1] 不是子数组。
分析
如果该题全为正数，那么就只是一道简单题，只要记录到i时乘积最大值即可。
但是该题存在负数，这就导致如果在i处，且nums[i]是个负数，此时乘积最大值是由前面的某个负数乘积 乘以 当前nums[i]而来，而如果我们只记录乘积的最大值，我们是会丢失掉负数乘积的。
因此，我们可以维护两个数组plusMax[],minusMin[]，分别记录正负数的绝对值最大值。
这样，如果nums[i]是负数，那么乘积最大可能由minusMin[i-1] * nums[i]得到，负负得正嘛。而如果nums[i]是正数，那么乘积最大可能由plusMax[i-1] * nums[i]得到。而对于上述两种情况，我们都要不断更新绝对值最大的负数。
当然，最大值也可能是单独某一个nums[i]的值。
转移方程如下：
- plusMax(i) = max(plus[i-1]*nums[i],minusMin[i-1]*nums[i],nums[i])
- minusMin(i) = min(plus[i-1]*nums[i],minusMin[i-1]*nums[i],nums[i])
代码
class Solution {
public int maxProduct(int[] nums) {
if(nums.length==1){
return nums[0];
}
int[] plusMax = new int[nums.length];
int[] minusMin = new int[nums.length];
plusMax[0] = nums[0];
minusMin[0] = nums[0];
int max=nums[0];
for(int i=1;i<nums.length;i++){
plusMax[i] = Math.max(Math.max(plusMax[i-1]*nums[i],minusMin[i-1]*nums[i]),nums[i]);
minusMin[i] = Math.min(Math.min(plusMax[i-1]*nums[i],minusMin[i-1]*nums[i]),nums[i]);
max = Math.max(Math.max(plusMax[i],minusMin[i]),max);
}
return max;
}
}