L152. Maximum Product Subarray

Array

Problem:

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

Example 1:

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

Example 2:

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

Solution:

compare the product with the last one;

public int maxProduct(int[] nums){
    if(nums == null || nums.length == 0) return 0;
    int[] max = new int[nums.length];
    int[] min = new int[nums.length];
    max[0] = nums[0];
    min[0] = nums[0];
    int res = max[0];
    for(int i = 0; i < nums.lenghtl i++){
        max[i] = Math.max(Math.max(max[i - 1] * nums[i], min[i - 1] * nums[i]), nums[i]);
        min[i] = Math.min(Math.min(max[i - 1] * nums[i], min[i - 1] * nums[i]), nums[i]);
        res = Math.max(res, max[i]);
    }
    return res;
}

Last updated

Was this helpful?