Day 11 - Maximum Product Subarray.md

Difficulty	Source	Tags
Medium	160 Days of Problem Solving	Arrays

🚀 Day 11. Maximum Product Subarray 🧠

The problem can be found at the following link: Problem Link

💡 Problem Description:

Given an array arr[] that contains both positive and negative integers (and possibly zeros), find the maximum product of any subarray within the array.

Note: The result will always fit within the range of a 32-bit integer.

🔍 Example Walkthrough:

Input:
arr[] = [-2, 6, -3, -10, 0, 2]
Output:
180

Explanation:
The subarray with the maximum product is {6, -3, -10} with product = 6 * (-3) * (-10) = 180.

Input:
arr[] = [-1, -3, -10, 0, 60]
Output:
60

Explanation:
The subarray with the maximum product is {60}.

Input:
arr[] = [2, 3, 4]
Output:
24

Explanation:
For an array with all positive elements, the result is the product of all elements.

Constraints:

• $1 ≤ arr.size() ≤ 10^6$
• $-10 ≤ arr[i] ≤ 10$

🎯 My Approach:

1. Dynamic Programming with Two Variables (maxVal, minVal):
   The idea is to track the maximum and minimum product subarrays up to the current index. The minimum product may become the maximum product if multiplied by a negative number.

2. Steps:

   • Traverse the array, updating the maxVal and minVal at each step based on the current number.
   • If the current number is negative, we swap maxVal and minVal.
   • Update maxProduct after processing each element to keep track of the overall maximum product encountered.

🕒 Time and Auxiliary Space Complexity 📝

• Expected Time Complexity: O(n), where n is the size of the array. The algorithm requires a single pass through the array, making it efficient.
• Expected Auxiliary Space Complexity: O(1), as we use a constant amount of extra space.

📝 Solution Code

Code (C)

int maxProduct(int arr[], int n) {
    int maxProduct = arr[0];
    int maxVal = arr[0], minVal = arr[0];

    for (int i = 1; i < n; ++i) {
        if (arr[i] < 0) {
            int temp = maxVal;
            maxVal = minVal;
            minVal = temp;
        }

        maxVal = (arr[i] > maxVal * arr[i]) ? arr[i] : maxVal * arr[i];
        minVal = (arr[i] < minVal * arr[i]) ? arr[i] : minVal * arr[i];

        maxProduct = (maxProduct > maxVal) ? maxProduct : maxVal;
    }

    return maxProduct;
}

Code (Cpp)

class Solution {
public:
    int maxProduct(vector<int>& nums) {
        int maxProduct = nums[0];
        int maxVal = nums[0], minVal = nums[0];

        for (int i = 1; i < nums.size(); ++i) {
            if (nums[i] < 0) {
                std::swap(maxVal, minVal);
            }

            maxVal = std::max(nums[i], maxVal * nums[i]);
            minVal = std::min(nums[i], minVal * nums[i]);

            maxProduct = std::max(maxProduct, maxVal);
        }

        return maxProduct;
    }
};

👨‍💻 Alternative Approaches

class Solution {
public:
    int maxProduct(vector<int>& arr) {
        int n = arr.size();
        int maxProduct = arr[0], maxVal = arr[0], minVal = arr[0];

        for (int i = 1; i < n; ++i) {
            int current = arr[i];

            if (current < 0) swap(maxVal, minVal);

            maxVal = max(current, maxVal * current);
            minVal = min(current, minVal * current);

            maxProduct = max(maxProduct, maxVal);
        }

        return maxProduct;
    }
};

class Solution {
public:
    int maxProduct(vector<int>& arr) {
        int n = arr.size();
        int maxProduct = arr[0], maxVal = arr[0], minVal = arr[0];

        for (int i = 1; i < n; ++i) {
            int current = arr[i];

            if (current < 0) {
                int temp = maxVal;
                maxVal = minVal;
                minVal = temp;
            }

            maxVal = (current > maxVal * current) ? current : maxVal * current;
            minVal = (current < minVal * current) ? current : minVal * current;

            if (maxVal > maxProduct) {
                maxProduct = maxVal;
            }
        }

        return maxProduct;
    }
};

Code (Java)

class Solution {

    int maxProduct(int[] nums) {
        int maxProduct = nums[0];
        int maxVal = nums[0];
        int minVal = nums[0];

        for (int i = 1; i < nums.length; i++) {
            if (nums[i] < 0) {

                int temp = maxVal;
                maxVal = minVal;
                minVal = temp;
            }

            maxVal = Math.max(nums[i], maxVal * nums[i]);
            minVal = Math.min(nums[i], minVal * nums[i]);

            maxProduct = Math.max(maxProduct, maxVal);
        }

        return maxProduct;
    }
}

Code (Python)

class Solution:

    def maxProduct(self, arr):
        max_product = arr[0]
        max_val = arr[0]
        min_val = arr[0]

        for i in range(1, len(arr)):
            if arr[i] < 0:
                max_val, min_val = min_val, max_val

            max_val = max(arr[i], max_val * arr[i])
            min_val = min(arr[i], min_val * arr[i])

            max_product = max(max_product, max_val)

        return max_product

🎯 Contribution and Support:

For discussions, questions, or doubts related to this solution, feel free to connect on LinkedIn: Any Questions. Let’s make this learning journey more collaborative!

⭐ If you find this helpful, please give this repository a star! ⭐

---

📍Visitor Count