[LeetCode] Problem 152 - Maximum Product Subarray

Posted on | In ,

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

Example

No.1

Input: [2,3,-2,4]

Output: 6

Explanation: [2,3] has the largest product 6.

No.2

Input: [-2,0,-1]

Output: 0

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

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public int maxProduct(int[] nums) {
    int[][] dp = new int[nums.length][2];
    int max = nums[0];
    dp[0][0] = dp[0][1] = nums[0];

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

    return max;
}