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.

Constraints

Approach

Links

• GeeksforGeeks

• Leetcode

• ProgramCreek

• YouTube

Examples

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.

Solutions

Solution 1

/**
 * Time complexity : O(N^2) where N is the size of nums. Since we are 
 *    checking every possible contiguous subarray following every element 
 *    in nums we have quadratic runtime.
 * Space complexity : O(1) since we are not consuming additional space other 
 *    than two variables: result to hold the final result and accu to 
 *    accumulate product of preceding contiguous subarrays.
 */

class Solution {
    public int maxProduct(int[] nums) {
        if (nums.length == 0) return 0;

        int result = nums[0];

        for (int i = 0; i < nums.length; i++) {
            int accu = 1;
            for (int j = i; j < nums.length; j++) {
                accu *= nums[j];
                result = Math.max(result, accu);
            }
        }

        return result;
    }
}

Solution 2

/**
 * Time complexity : O(N)
 * Space complexity : O(1)
 */

class Solution {
    public int maxProduct(int[] nums) {
        int res = nums[0], min = nums[0], max = nums[0];
        for(int i = 1; i < nums.length; i++) {
            int tmp = max;
            int n = nums[i];
            
            max = Math.max(Math.max(n, max*n), min*n);
            min = Math.min(Math.min(n, min*n), tmp*n);
            
            if(max > res) res = max;
        }
        return res;
    }
}

Follow up