152 乘积最大子序列.md

152 乘积最大子序列

题目：

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

示例1：

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

示例2：

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

解题（动态规划）：

• 由于存在负数和整数，所以创建两个dp数组，分别存放最大值和最小值。当nums的值为负数时，存放最小值的dp就派上了用场，最小的负数转换成最大的正数。

• 除了这个交换之外，和求最大子序列和没什么区别。

• res是用来存放阶段性最值的，其实也可以看成一个dp

public int maxProduct(int[] nums) {
        if(nums==null || nums.length==0) return 0;

        //返回值，用来存放阶段性最大值
        int res = Integer.MIN_VALUE;
        
        //创建两个数组，分别存放阶段性最大值和最小值的累乘
        int[] dp_max = new int[nums.length+1];
        int[] dp_min = new int[nums.length+1];
        
        dp_max[0] = 1;
        dp_min[0] = 1;

        //dp的循环
        for(int i=1; i<=nums.length; i++){
            //如果当前的nums[i-1]小于0，那么就交换
            if(nums[i-1]<0){
                int temp = dp_max[i-1];
                dp_max[i-1] = dp_min[i-1];
                dp_min[i-1] = temp;
            }

            dp_max[i] = Math.max(dp_max[i-1]*nums[i-1], nums[i-1]);
            dp_min[i] = Math.min(dp_min[i-1]*nums[i-1], nums[i-1]);

            res = Math.max(res, dp_max[i]);
        }

        return res;
    }