Max Product Subarray

Problem Overview

The problem we are tackling is known as "Maximum Product Subarray." While the title is not explicitly provided, the problem falls under the domain of Dynamic Programming and is known for its unique challenge of identifying the contiguous subarray within a one-dimensional array of integers which has the largest product.

Understanding the Problem

Given an integer array nums, the problem requires us to find the contiguous subarray (containing at least one number) which has the largest product and return that product.

Example

For instance, consider the array nums = [2, 3, -2, 4]. The largest product of a contiguous subarray is 6, which is derived from the subarray [2, 3].

Key Points:

• The array can include positive, negative numbers, and zero.
• The product of an even count of negative numbers yields a positive product.
• The presence of zeroes can be disruptive, resetting the product counts.

Key DSA Concepts and Theory

Dynamic Programming

Dynamic programming is a method for solving problems by breaking them down into simpler subproblems, storing the results of subproblems to avoid redundant calculations. It is particularly useful in optimization problems. We will maintain two arrays (or variables) to keep track of the maximum and minimum products at each element because the negative number can lead to a larger product when multiplied by another negative one.

Array Traversal

We'll be traversing the array from the start to the end while maintaining a current maximum and minimum product, adapting dynamically as we progress through different elements of the array.

Solution Approach

Step-by-step Solution

1. Initialization: We initialize two variables, curMax and curMin, to keep track of the current maximum and minimum products at each position. Both are initially set to the first element of the array. We also initialize globalMax as the first element.

2. Traverse the Array: From the second element to the end of the array, we update the current products:

   • If the current element is negative, we swap curMax and curMin because a negative number will make a large negative product positive and a small positive product smaller.
   • Update curMax as the maximum between the current number and the product of curMax with the current number.
   • Update curMin as the minimum between the current number and the product of curMin with the current number.
   • Update the globalMax as the maximum between itself and curMax.

3. Return Result: After finishing the traversal, globalMax holds the result of the maximum product subarray.

C++ Code

#include <vector>
#include <algorithm>
using namespace std;

int maxProduct(vector<int>& nums) {
    if (nums.empty()) return 0;
    int curMax = nums[0], curMin = nums[0], globalMax = nums[0];

    for (size_t i = 1; i < nums.size(); ++i) {
        if (nums[i] < 0) {
            swap(curMax, curMin);
        }
        curMax = max(nums[i], curMax * nums[i]);
        curMin = min(nums[i], curMin * nums[i]);

        globalMax = max(globalMax, curMax);
    }
    return globalMax;
}

Java Code

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

        for (int i = 1; i < nums.length; i++) {
            if (nums[i] < 0) {
                int temp = curMax;
                curMax = curMin;
                curMin = temp;
            }
            curMax = Math.max(nums[i], curMax * nums[i]);
            curMin = Math.min(nums[i], curMin * nums[i]);

            globalMax = Math.max(globalMax, curMax);
        }
        return globalMax;
    }
}

Time and Space Complexity Analysis

Time Complexity

The solution requires a single pass over the nums array, resulting in a time complexity of O(n), where n is the number of elements in the array.

Space Complexity

The solution has a space complexity of O(1) since it uses a constant amount of space, storing only a few variables for tracking the current state.

Common Mistakes to Avoid

• Ignoring Negative Numbers: Always handle the swapping of curMax and curMin when encountering a negative number.
• Zero Handling: Reset the curMax and curMin to the current element when encountering a zero in the array.

Similar Problems on LeetCode

• 53. Maximum Subarray
• 152. Maximum Product Subarray
• 628. Maximum Product of Three Numbers

Additional Resources and References

• GeeksforGeeks on Maximum Product Subarray
• Dynamic Programming: Practice Problems on LeetCode
• LeetCode Discuss for varied solution approaches and insights from the community.

By understanding these aspects thoroughly, you will be better prepared to tackle the "Maximum Product Subarray" problem and similar dynamic programming challenges!