152. 乘积最大子数组

题目:

给你一个整数数组 nums ，请你找出数组中乘积最大的连续子数组（该子数组中至少包含一个数字），并返回该子数组所对应的乘积。

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

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

思路:

• 遍历数组时计算当前最大值，不断更新
• 我们需要记录阶段子数组最大值和最小值,当出现负数的时候我们阶段最大值×负数会变成阶段最小值,阶段最小值×负数会变阶段最大值,因此我们需要存储阶段最小值,并且在需要负数的时候进行提取的交换,不影响后续处理逻辑

代码:

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

        int max=nums[0],itemMax=nums[0],itemMin=nums[0];
        //max 存储所有连续子数组最大值
        //itemMax,itemMin存储当前子数组最大值和最小值
        //其中需要itemMin存最小值主要因为数组里可能有负数,负数最小值再乘以一个整数就是最大值
        for (int i = 1; i < nums.length; i++) {
            if (nums[i]<0){
                int temp=itemMin;
                itemMin=itemMax;
                itemMax=temp;
            }

            itemMax=Math.max(itemMax*nums[i],nums[i]);
            itemMin=Math.min(itemMin*nums[i],nums[i]);

            max=Math.max(max,itemMax);
        }
        return max;
    }