Maximum Product Subarray medium

Problem Statement

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: nums = [2,3,-2,4] Output: 6 Explanation: [2,3] has the largest product 6.

Example 2:

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

Steps and Explanation

This problem can't be solved using the typical Kadane's algorithm for maximum sum subarray because multiplying negative numbers can lead to a larger product than expected. We need to track both the maximum and minimum products so far. At each position, we consider three possibilities:

1. The current number itself: This is especially important if the current number is positive and the previous product was negative.
2. The current number multiplied by the maximum product so far: This extends a positive product sequence.
3. The current number multiplied by the minimum product so far: This is important if the current number is negative; a negative number multiplied by a negative number can result in a positive and potentially larger product.

We maintain two variables: max_so_far and min_so_far. max_so_far keeps track of the maximum product ending at the current position, and min_so_far keeps track of the minimum product ending at the current position (this is crucial for handling negative numbers). We update these variables iteratively.

The overall maximum product will be the maximum of all max_so_far values encountered during the iteration.

Code (C++)

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int maxProduct(vector<int>& nums) {
    int n = nums.size();
    if (n == 0) return 0;

    int max_so_far = nums[0];
    int min_so_far = nums[0];
    int max_product = nums[0];

    for (int i = 1; i < n; i++) {
        int temp_max = max({nums[i], nums[i] * max_so_far, nums[i] * min_so_far});
        int temp_min = min({nums[i], nums[i] * max_so_far, nums[i] * min_so_far});
        max_so_far = temp_max;
        min_so_far = temp_min;
        max_product = max(max_product, max_so_far);
    }
    return max_product;
}

int main() {
    vector<int> nums1 = {2, 3, -2, 4};
    cout << "Max product for " << "[";
    for (int x : nums1) cout << x << ",";
    cout << "] is: " << maxProduct(nums1) << endl; // Output: 6

    vector<int> nums2 = {-2, 0, -1};
    cout << "Max product for " << "[";
    for (int x : nums2) cout << x << ",";
    cout << "] is: " << maxProduct(nums2) << endl; // Output: 0

    vector<int> nums3 = {-2,3,-4};
    cout << "Max product for " << "[";
    for (int x : nums3) cout << x << ",";
    cout << "] is: " << maxProduct(nums3) << endl; // Output: 24

    return 0;
}

Complexity Analysis

• Time Complexity: O(n), where n is the length of the input array. We iterate through the array once.
• Space Complexity: O(1). We use only a few constant extra variables.