Leetcode(152) Maximum Product Subarray

发表于 | 分类于

Description

Given an integer array nums, find the contiguous subarray within an array (containing at least one number) which has the largest product.

Example 1:

1
2
3
Input: [2,3,-2,4]
Output: 6
Explanation: [2,3] has the largest product 6.

Example 2:

1
2
3
Input: [-2,0,-1]
Output: 0
Explanation: The result cannot be 2, because [-2,-1] is not a subarray.

解法

最开始想着这不是简单的动态规划吗，然后就掉坑里了，因为存在相乘时负负得正的情况，所以需要同时记录当前位置累积的最小值与最大值，并且先更新最小值，再更新最大值可以得到正确的结果

具体代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public int maxProduct(int[] nums) {
        if (nums.length == 0) {
            return 0;
        }
        int[] dpmax = new int[nums.length];
        int[] dpmin = new int[nums.length];
        dpmax[0] = nums[0];
        dpmin[0] = nums[0];
        for (int i = 1; i < nums.length; i++) {
            dpmin[i] = Math.min(dpmax[i - 1] * nums[i], Math.min(nums[i], dpmin[i - 1] * nums[i]));
            dpmax[i] = Math.max(dpmin[i - 1] * nums[i], Math.max(nums[i], dpmax[i - 1] * nums[i]));
        }
        int res = Integer.MIN_VALUE;
        for (int i = 0; i < nums.length; i++) {
            res = dpmax[i] > res ? dpmax[i] : res;
        }
        return res;
    }
}