152. Maximum Product Subarray: Leetcode Step-by-Step Approach

Maximum Product Subarray - LeetCode

Photo by Ella Jardim on Unsplash

PROBLEM STATEMENT:

Given an integer array nums, find a subarray 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.

APPROACH:

1. Initialization:

• ans is initialized to the first element of the array, as it could be the maximum product itself.
• ma and mi are both initialized to the value of ans.

2. Iteration:

• The loop iterates through the array starting from the second element (index 1).
• For each element nums[i] :
• If nums[i] <0 , it indicates a potential change in the sign of the product. To handle this case, swap ma and mi values. This ensures that ma always holds the maximum positive product and mi always holds the maximum negative product.
• Update the ma and mi values.
• After updating ma and mi, compare the current value of ma with the current value of ans. If ma is greater than ans, update ans to reflect the new maximum product.

3. Return Value:

• The function returns the final value of ans, which represents the maximum product of any subarray within the given array.

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

class Solution {
public:
    int maxProduct(std::vector<int>& nums) {
        int ans = nums[0];
        int ma = ans;
        int mi = ans;

        for(int i=1; i<nums.size(); i++){
            if(nums[i]<0){
                std::swap(ma, mi);
            }
            ma = std::max(nums[i], ma * nums[i]);
            mi = std::min(nums[i], mi * nums[i]);

            ans = std::max(ma, ans);
        }

        return ans;
    }
};

int main() {
    Solution solution;
    
    std::vector<int> nums = {2, 3, -2, 4, -1};
    
    std::cout << "Maximum product of subarray: " << solution.maxProduct(nums) << std::endl;
    
    return 0;
}

TIME COMPLEXITY: O(N)