[LeetCode 152] Maximum Product Subarray [Java] [Runtime : 2MS]

1. Description

Find the contiguous subarray within an array (containing at least one number) which has the largest product.

2. Runtime Distribution

3. Submission Details

4. Example

given the array [2,3,-2,4]
the contiguous subarray [2,3] has the largest product = 6.

5. Explanation

DP

Let dpMax[i] stands for the max product which the contiguous subarray end at i.
Let dpMin[i] stands for the min product which the contiguous subarray end at i.

(1)、 $dpMax[0] = dpMin[0] = nums[0]$
(2)、 $for(i : 1 \\rightarrow N)$
$temp1 = dpMax[i - 1] \\times nums[i];$
$temp2 = dpMin[i - 1] \\times nums[i];$
$dpMax[i] = max \\{ temp1, temp2, nums[i] \\};$
$dpMin[i] = min \\{ temp1, temp2, nums[i] \\};$

6. Code


public class LeetCode0152 {

    public int maxProduct(int[] nums) {

        if (nums == null || nums.length == 0) {
            return 0;
        }

        int min = nums[0];
        int max = nums[0];
        int result = max;

        for (int i = 1; i < nums.length; i++) {

            int small = min * nums[i];
            int large = max * nums[i];

            if (large < small) {
                int tmp = large;
                large = small;
                small = tmp;
            }
            min = Math.min(small, nums[i]);
            max = Math.max(large, nums[i]);

            if (max > result) {
                result = max;
            }
        }
        return result;
    }

    public static void main(String[] args) {
        int nums[] = { 2, 3, -2, 4 };
        LeetCode0152 leetcode = new LeetCode0152();
        System.out.println(leetcode.maxProduct(nums));
    }

}