LeetCode 0152. 乘积最大子数组[动态规划详解]

原创

Yano_nankai

修改于 2021-04-12 10:58:48

5960

修改于 2021-04-12 10:58:48

文章被收录于专栏：二进制文集二进制文集

题目描述

题目链接

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

示例 1:

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

示例 2:

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

解题思路

本题要求的是「乘积最大的子数组」，但是最大的乘积可能是两个正数相乘，也可能是两个负数相乘。定义 pi 为包含 i 的子数组最大乘积，ni 为包含 i 的子数组最小乘积。则记数组 nums0:i 的最大乘积值为 m：

pi = max(pi - 1 numsi, numsi, ni - 1 numsi)
ni = min(pi - 1 numsi, numsi, ni - 1 numsi)
m = max(m, pi)

代码

class Solution {
    public int maxProduct(int[] nums) {
        int[] p = new int[nums.length];
        int[] n = new int[nums.length];
        int max = nums[0];
        p[0] = nums[0];
        n[0] = nums[0];
        for (int i = 1; i < nums.length; i++) {
            p[i] = Math.max(Math.max(p[i - 1] * nums[i], nums[i]), n[i - 1] * nums[i]);
            n[i] = Math.min(Math.min(p[i - 1] * nums[i], nums[i]), n[i - 1] * nums[i]);
            max = Math.max(max, p[i]);
        }
        return max;
    }
}