leetcode152_乘积最大子序列

给定一个整数数组 nums ，找出一个序列中乘积最大的连续子序列（该序列至少包含一个数）。

示例 1:

输入: [2,3,-2,4]
输出: 6
解释: 子数组 [2,3] 有最大乘积 6。
示例 2:

输入: [-2,0,-1]
输出: 0
解释: 结果不能为 2, 因为 [-2,-1] 不是子数组

思路：

本题是求最大乘积，是最大子段和的变种。最大乘积可以由   正数*正数 和 负数*负数得到，因此，需要同时记录下最大值和最小值。 状态转移方程：

   res= max(max*nums[i],min*nums[i],dp[i-1])

    max = max(max*nums[i],min*nums[i],nums[i])

    min = min(max*nums[i],min*nums[i],nums[i])

    public int maxProduct(int[] nums) {
		if (nums == null || nums.length == 0)
			return 0;
		int res =  nums[nums.length - 1];
		int max= nums[nums.length - 1];
		int min= nums[nums.length - 1];
		for (int i = nums.length - 2; i >= 0; i--) {
			if (nums[i] >= 0) { 
				max=Math.max(nums[i], nums[i]*max); 
				min=Math.min(nums[i], nums[i]*min);          
			}else {  //为负数
				int temp=max;  //保存一下max
				max=Math.max(nums[i], min*nums[i]);
				min=Math.min(nums[i], temp*nums[i]);
			}
			 res=Math.max(max, res);
		}
		return res;
	}