DEV Community

Alkesh Ghorpade
Alkesh Ghorpade

Posted on • Originally published at alkeshghorpade.me

LeetCode - Maximum Product Subarray

Problem statement

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

The test cases are generated so that the answer will fit in a 32-bit integer.

A subarray is a contiguous subsequence of the array.

Problem statement taken from: https://leetcode.com/problems/maximum-product-subarray.

Example 1:

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

Example 2:

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

Constraints:

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

Explanation

Brute Force approach

A simple approach is to consider all subarrays and return the maximum product.

A C++ snippet of the approach will look as below:

int result = arr[0];

for (int i = 0; i < n; i++) {
    int mul = arr[i];

    for (int j = i + 1; j < n; j++) {
        result = max(result, mul);
        mul *= arr[j];
    }

    result = max(result, mul);
}

return result;
Enter fullscreen mode Exit fullscreen mode

The time-complexity of the above approach is O(N^2), and space complexity is O(1).

Efficient approach

The efficient approach is similar to what we have used in our previous blog post Maximum Subarray. An important thing to notice here is an array can contain both positive and negative numbers as well as zero. The maximum subarray problem used Kadane's algorithm. We tweak this approach and instead use three variables called as max_so_far, max_ending_here and min_ending_here. For each index the maximum number ending at that index will be maximum(arr[i], max_ending_here * arr[i], min_ending_here * arr[i]). Similarly, the minimum number ending here will be the minimum of these 3.

Let's check the algorithm first.

- set max_ending_here, min_ending_here and max_so_far to nums[0]
  initialize temp_maximum

- loop for i = 1; i < nums.size(); i++
  - temp_maximum = max(nums[i], nums[i] * max_ending_here, nums[i] * min_ending_here)
  - min_ending_here = min(nums[i], nums[i] * max_ending_here, nums[i] * min_ending_here)
  - max_ending_here = temp_maximum
  - max_so_far = max(max_so_far, max_ending_here)

- return max_so_far
Enter fullscreen mode Exit fullscreen mode

Let's check out our solutions in C++, Golang, and Javascript.

C++ solution

class Solution {
public:
    int maxProduct(vector<int>& nums) {
        int max_ending_here = nums[0];
        int min_ending_here = nums[0];
        int max_so_far = nums[0];
        int temp_maximum;

        for(int i = 1; i < nums.size(); i++) {
            temp_maximum = max({nums[i], nums[i] * max_ending_here, nums[i] * min_ending_here});
            min_ending_here = min({nums[i], nums[i] * max_ending_here, nums[i] * min_ending_here});
            max_ending_here = temp_maximum;
            max_so_far = max(max_so_far, max_ending_here);
        }

        return max_so_far;
    }
};
Enter fullscreen mode Exit fullscreen mode

Golang solution

func max(a, b int) int {
    if a > b {
        return a
    }

    return b
}

func min(a, b int) int {
    if a < b {
        return a
    }

    return b
}

func maxProduct(nums []int) int {
    max_ending_here, min_ending_here, max_so_far := nums[0], nums[0], nums[0]
    var temp_maximum int

    for i := 1; i < len(nums); i++ {
        temp_maximum = max(nums[i], max(max_ending_here * nums[i], min_ending_here * nums[i]))
        min_ending_here = min(nums[i], min(max_ending_here * nums[i], min_ending_here * nums[i]))
        max_ending_here = temp_maximum
        max_so_far = max(max_so_far, max_ending_here)
    }

    return max_so_far
}
Enter fullscreen mode Exit fullscreen mode

Javascript solution

var maxProduct = function(nums) {
    let max_ending_here = nums[0], min_ending_here = nums[0], max_so_far = nums[0];
    let temp_maximum

    for(let i = 1; i < nums.length; i++) {
        temp_maximum = Math.max(nums[i], Math.max(max_ending_here * nums[i], min_ending_here * nums[i]));

        min_ending_here = Math.min(nums[i], Math.min(max_ending_here * nums[i], min_ending_here * nums[i]));

        max_ending_here = temp_maximum;
        max_so_far = Math.max(max_so_far, max_ending_here)
    }

    return max_so_far;
};
Enter fullscreen mode Exit fullscreen mode

Let's dry-run our algorithm to see how the solution works.

Input: nums = [2, 3, -2, 4]

Step 1: max_ending_here, min_ending_here, max_so_far = nums[0], nums[0], nums[0]
        max_ending_here = 2
        min_ending_here = 2
        max_so_far = 2

        initialize temp_maximum

Step 2: loop for i = 1; i < nums.size()
        i < nums.size()
        1 < 4
        true

        temp_maximum = max(nums[i], nums[i] * max_ending_here, nums[i] * min_ending_here)
                     = max(nums[1], nums[1] * 2, nums[1] * 2)
                     = max(3, 3 * 2, 3 * 2)
                     = max(3, 6, 6)
                     = 6

        min_ending_here = min(nums[i], nums[i] * max_ending_here, nums[i] * min_ending_here)
                        = min(nums[1], nums[1] * 2, nums[1] * 2)
                        = min(3, 3 * 2, 3 * 2)
                        = min(3, 6, 6)
                        = 3

        max_ending_here = temp_maximum
                        = 6

        max_so_far = max(max_so_far, max_ending_here)
                   = max(2, 6)
                   = 6

        i++
        i = 2

Step 3: loop for i < nums.size()
        i < nums.size()
        2 < 4
        true

        temp_maximum = max(nums[i], nums[i] * max_ending_here, nums[i] * min_ending_here)
                     = max(nums[2], nums[2] * 6, nums[2] * 3)
                     = max(-2, -2 * 6, -2 * 3)
                     = max(-2, -12, -6)
                     = -2

        min_ending_here = min(nums[i], nums[i] * max_ending_here, nums[i] * min_ending_here)
                        = min(nums[2], nums[2] * 6, nums[2] * 3)
                        = min(-2, -2 * 6, -2 * 3)
                        = min(-2, -12, -6)
                        = -12

        max_ending_here = temp_maximum
                        = -2

        max_so_far = max(max_so_far, max_ending_here)
                   = max(6, -2)
                   = 6

        i++
        i = 3

Step 4: loop for i < nums.size()
        i < nums.size()
        3 < 4
        true

        temp_maximum = max(nums[i], nums[i] * max_ending_here, nums[i] * min_ending_here)
                     = max(nums[3], nums[3] * -2, nums[3] * -12)
                     = max(4, 4 * -2, 4 * -12)
                     = max(4, -8, -48)
                     = 4

        min_ending_here = min(nums[i], nums[i] * max_ending_here, nums[i] * min_ending_here)
                        = min(nums[3], nums[3] * -2, nums[3] * -12)
                        = min(4, 4 * -2, 4 * -12)
                        = min(4, -8, -48)
                        = -48

        max_ending_here = temp_maximum
                        = 4

        max_so_far = max(max_so_far, max_ending_here)
                   = max(6, 4)
                   = 6

        i++
        i = 4

Step 5: loop for i < nums.size()
        i < nums.size()
        4 < 4
        false

Step 6: return max_so_far

So we return the answer as 6.
Enter fullscreen mode Exit fullscreen mode

Top comments (0)