Problem

Given an integer array nums. Find the subarray with the largest product, and return the product of the elements present in that subarray.

A subarray is a contiguous non-empty sequence of elements within an array.

Examples

Example: 1

Input: nums = [4, 5, 3, 7, 1, 2]
Output: 840

Explanation: The largest product is given by the whole array itself.

Example: 2

Input: nums = [-5, 0, -2]
Output: 0

Explanation: The largest product is achieved with the following subarray [0].

Different Approaches

1️⃣ Brute Force Approach

Intuition:

The naive way is to identify all possible subarrays using nested loops. For each subarray, calculate the product of its elements. Ultimately, return the maximum product found among all subarrays.

Approach:

1. Iterate in the array using i which runs from 0 to sizeOfArray - 1, it will basically identify the starting point of the subarrays.
2. Now run an inner loop using j from i+1 to sizeOfArray - 1, it will identify the ending point of the subarrays. Inside this loop, iterate again from i to j and multiply elements present in the chosen range.
3. Update the maximum product after each iteration and finally, return it.

Code:

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    // Function to find maximum product subarray
    int maxProduct(vector<int>& nums) {
        
        // Initialize result to minimum possible integer
        int result = INT_MIN; 
        
        // Iterate through all subarrays 
        for (int i = 0; i < nums.size() - 1; i++) {
            for (int j = i + 1; j < nums.size(); j++) {
                int prod = 1;
                
                // Calculate product of subarray 
                for (int k = i; k <= j; k++) {
                    prod *= nums[k];
                }
                
                // Update the result with maximum product found
                result = max(result, prod);
            }
        }
        
        // Return the maximum product found
        return result;
    }
};

int main() {
    vector<int> nums = {4, 5, 3, 7, 1, 2};
    
    // Create an instance of the Solution class
    Solution sol;

    int maxProd = sol.maxProduct(nums);
    
    // Print the result
    cout << "The maximum product subarray: " << maxProd << endl;
    
    return 0;
}

Complexity Analysis:

• Time Complexity: O(N^3) for using 3 nested loops for finding all possible subarrays and their product. Here N is the size of the array.
• Space Complexity: O(1), as no additional space is used apart from the input array.

2️⃣ Better Approach

Intuition:

A better idea is to maximize the product using two loops. In the innermost loop of the brute-force solution, observe that we calculate the product of subarrays starting from index i to j. However, it can be optimized by computing the product incrementally. Multiplying arr[j] in the second loop with the previous product. This approach improves the time complexity of the solution.

Approach:

1. Iterate in the array using i which starts from 0 and goes till sizeOfArray - 1. Now, iterate in array using an inner loop using j, which starts from i+1 and goes till sizeOfArray - 1. Initialize a variable prod to store product and max to store maximum product.
2. Inside this loop, multiply arr[j] to prod variable in each iteration and update the max variable each time. Finally, return max variable as an answer.

Code:

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    // Function to find maximum product subarray
    int maxProduct(vector<int>& nums) {
        
        // Initialize result with first element of nums
        int result = nums[0]; 
        
        /* Iterate through each element
        as a starting point of subarray*/
        for (int i = 0; i < nums.size() - 1; i++) {
            
            // Initialize p with nums[i]
            int p = nums[i];

            /* Iterate through subsequent elements 
            to form subarrays starting from nums[i]*/
            for (int j = i + 1; j < nums.size(); j++) {
                
                /* Update result with the 
                max of current result and p*/
                result = max(result, p);
                
                // Update p by multiplying with nums[j]
                p *= nums[j]; 
            }
            
            // Update result for subarray ending at nums[i]
            result = max(result, p); 
        }
        
        // Return maximum product subarray found
        return result; 
    }
};

int main() {
    vector<int> nums = {4, 5, 3, 7, 1, 2};
    
    // Create an instance of the Solution class
    Solution sol;
  
    int maxProd = sol.maxProduct(nums);
    
    // Print the result
    cout << "The maximum product subarray: " << maxProd << endl;
    
    return 0;
}

Complexity Analysis:

• Time Complexity: O(N^2) for using 2 nested loops for finding all possible subarrays and their product. Here N is the size of the array.
• Space Complexity: O(1) as no additional space is used apart from the input array.