0152 - Maximum Product Subarray

0152 - Maximum Product Subarray

Given an integer array nums, find a contiguous non-empty subarray within the array that has the largest product, and return the product.

It is guaranteed that the answer will fit in a 32-bit integer.

A subarray is a contiguous subsequence of the array.

Examples

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

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

Constraints

1 <= nums.length <= 2 * 104 -10 <= nums[i] <= 10 The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer.

Java Solution

Dynamic Programming

class Solution {
    public int maxProduct(int[] nums) {
        
        int max = nums[0];
        int min = nums[0];
        int result = max;

        for (int i = 1; i < nums.length; i++) {
            int current = nums[i];
            int tempmax = Math.max(current, Math.max(max*current, min*current));
            min = Math.min(current, Math.min(max*current, min*current));
            
            max = tempmax;
            result = Math.max(result, max);
        }

        return result;
    }
}

Brute Force

class Solution {
    public int maxProduct(int[] nums) {
        int max = nums[0];
        for(int i = 0; i < nums.length; i++) {
            int tempMax = 1;
            for(int j = i; j < nums.length; j++) {
                tempMax *= nums[j];
                if(tempMax > max) max = tempMax;
            }
        }
        
        return max;
    }
}