ChunNote
0%

leetCode-152:Maximum Product Subarray

发表于 分类于

问题描述

给定一个整数数组，要求从数组中找出连续子数组，使得子数组中的元素乘积最大，将最大乘积值返回。题目链接：**点我**

样例输入输出

输入：[2,3,-2,4]

输出：6

输入：[-2,0,-1]

输出：0

问题解法

解决一：暴力

此问题最简单直接的方式，就是两层 for 循环直接暴力求解。代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution
{
    public int maxProduct(int[] nums)
    {
        int product = nums[0];
        for (int i = 0; i < nums.length; i++)
        {
            int current = nums[i];
            product = Math.max(current, product);
            for (int j = i + 1; j < nums.length; j++)
            {
                current = current * nums[j];
                product = Math.max(current, product);
            }
        }

        return product;
    }
}

解法二：动态规划

暴力求解比较耗时，稍微好点的方式是使用动态规划。此解法参考：

用 dpMaxs[i] 表示以 nums[i] 结尾的连续子数组的乘积的最大值，用 dpMins[i] 表示以 nums[i] 结尾的连续子数组的乘积的最小值。考虑 nums[i] 是正负数的情况。如果是正数，那前面的乘积必须得是正数，且值越大越好。如果是负数，那前面的乘积必须是负数，且值越小越好。所以就有以下的动态转换方程：

1
2
dpMaxs[i] = max(dpMaxs[i - 1] * nums[i], dpMins[i - 1] * nums[i], nums[i])
dpMins[i] = min(dpMaxs[i - 1] * nums[i], dpMins[i - 1] * nums[i], nums[i])

代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution
{
    public int maxProduct(int[] nums)
    {
        int[] dpMaxs = new int[nums.length];
        int[] dpMins = new int[nums.length];

        Arrays.fill(dpMaxs, Integer.MIN_VALUE);
        Arrays.fill(dpMins, Integer.MAX_VALUE);

        dpMaxs[0] = nums[0];
        dpMins[0] = nums[0];
        for (int i = 1; i < nums.length; i++)
        {
            dpMaxs[i] = Math.max(Math.max(dpMaxs[i - 1] * nums[i], dpMins[i - 1] * nums[i]), nums[i]);
            dpMins[i] = Math.min(Math.min(dpMaxs[i - 1] * nums[i], dpMins[i - 1] * nums[i]), nums[i]);
        }

        return Arrays.stream(dpMaxs).max().getAsInt();
    }
}

参考资料

https://leetcode-cn.com/problems/maximum-product-subarray/solution/cheng-ji-zui-da-zi-shu-zu-by-leetcode-solution/