leetcode152-乘积最大的子数组

152. 乘积最大子数组

已解答

中等

相关标签

相关企业

给你一个整数数组 nums ，请你找出数组中乘积最大的非空连续 

子数组

（该子数组中至少包含一个数字），并返回该子数组所对应的乘积。

测试用例的答案是一个 32-位 整数。

示例 1:

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

这道题因为安放在动态规划栏目里面，导致我先入为主直接开始动规四部曲，做完运行也成功，结果提交时候发现问题来了，我的动规就是从头向后找最大值，完全忽略了负数这码事，就导致两个负数的事例运行不了，所以要么重写要么给我再加一个dp数组。

所以我们暂且加一个dp数组，动规四部曲如下：

dp数组定义：一个max一个min，一个存放最大值一个存放最小值

递推公式：当小于0的时候需要最大值最小值交换，所以

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

                大于0的时候：

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

初始化就要把数组的第一位设成1或者设成nums[0]，这里我写的麻烦了一点就是设成了1，

遍历顺序从前向后，从后向前也一样，随个人喜好

上代码：

class Solution {
    public int maxProduct(int[] nums) {
        int n = nums.length;
        int[] dpmax = new int[n + 1];
        int[] dpmin = new int[n + 1];
        dpmax[0] = 1;
        dpmin[0] = 1;
        int res = Integer.MIN_VALUE;
        for (int i = 1; i <= n; i++) {
            if (nums[i-1] <= 0) {
                dpmax[i] = Math.max(nums[i-1],dpmin[i - 1] * nums[i - 1]);
                dpmin[i] = Math.min(nums[i-1],dpmax[i - 1] * nums[i - 1]);
            } else  {
                dpmax[i] = Math.max(nums[i-1],dpmax[i - 1] * nums[i - 1]);
                dpmin[i] = Math.min(nums[i-1],dpmin[i - 1] * nums[i - 1]);
            }
            res = Math.max(res, dpmax[i]);
        }
        return res;
    }

}

 写到这其实可以感受到其实没必要维护两个大数组，两个值其实就搞定了，所以更改一下

class Solution {
    public int maxProduct(int[] nums) {
        int n = nums.length;
        if (n == 0) return 0;

        // 初始化最大值和最小值
        int maxProd = nums[0];
        int minProd = nums[0];
        int result = nums[0];

        for (int i = 1; i < n; i++) {
            // 当前数字
            int num = nums[i];

            // 如果当前数字是负数，最大值和最小值会互换
            if (num < 0) {
                int temp = maxProd;
                maxProd = minProd;
                minProd = temp;
            }

            // 更新最大值和最小值
            maxProd = Math.max(num, maxProd * num);
            minProd = Math.min(num, minProd * num);

            // 更新结果
            result = Math.max(result, maxProd);
        }

        return result;
    }
}