2021-02-13 152. 乘积最大子数组

题目地址

https://leetcode-cn.com/problems/maximum-product-subarray/

题目描述

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

示例 1:
输入: [2,3,-2,4]
输出: 6
解释: 子数组 [2,3] 有最大乘积 6。
示例 2:
输入: [-2,0,-1]
输出: 0
解释: 结果不能为 2, 因为 [-2,-1] 不是子数组。

思路

1. 暴力法，从数组的每个位置开始计算乘积，存储最大值。相当于列举出了每一种case。
2. 动态规则，从0开始往后计算乘积，由于存在负数，最大值乘负数会变最小值，最小值乘负数会变最大值，因此需要维护当前计算的连续数组乘积的最大值和最小值。由于最大最小值可能重新开始计算，所以需要动态计算result。
   dpMax表示计算到当前位置，这一段里的连续乘积最大值（可能重新开始计算）
   dpMin表示计算到当前位置，这一段里的连续乘积的最小值（可能重新开始计算）

题解

/**
 * @Author: vividzcs
 * @Date: 2021/2/13 3:52 下午
 */
public class MaxProduct {
    public static void main(String[] args) {
        int[] nums = {-4,-3,-2};
        int result = maxProduct(nums);
        System.out.println(result);

        result = maxProductV2(nums);
        System.out.println(result);
    }

    /**
     * 动态规划
     */
    private static int maxProductV2(int[] nums) {
        int result = Integer.MIN_VALUE;
        int dpMax = 1; // 初始化为1是因为1乘任何数等于任何数
        int dpMin = 1;
        for (int i=0; i<nums.length; i++) {
            // 交换，因为最小值乘负数可能成为最大值
            if (nums[i] < 0) {
                int tmp = dpMax;
                dpMax = dpMin;
                dpMin = tmp;
            }
            dpMax = Math.max(dpMax * nums[i], nums[i]);
            dpMin = Math.min(dpMin * nums[i], nums[i]);
            // 上面求的dpMax和dpMin并不是从0开始计算的连续子数组乘积大小
            // dpMax和dpMin都可能重新开始计算
            // 所以result需要动态计算而不是最后返回dpMax
            result = Math.max(result, dpMax);
        }
        return result;
    }

    /**
     * 暴力解法
     */
    private static int maxProduct(int[] nums) {
        int result = Integer.MIN_VALUE;
        int tmpResult = result;
        for (int i=0; i<nums.length; i++) {
            tmpResult = nums[i];
            result = Math.max(result, tmpResult);
            for (int j=i+1; j<nums.length; j++) {
                tmpResult = tmpResult * nums[j];
                result = Math.max(result, tmpResult);
            }
        }
        return result;
    }
}