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

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

Follow up