Maximum Subarray Min Product - Leetcode Solution

Problem Statement: Given an array of n positive integers, find the maximum product of any contiguous subarray of the given array.

Example: Input: [1,2,3,2,1] Output: 8 Explanation: The maximum product subarray is [2,3,2] which gives 8 as the product.

Approach:

• For each element in the given array a, we need to find the contiguous subarray ending at that element such that its product is maximum.
• Let's assume that the subarray ends at index i. We need to find the left and right boundaries of this subarray such that all the elements in this subarray are greater than or equal to a[i].
• We can use two arrays left and right such that left[i] is the index of the closest element on its left such that its value is less than a[i] and right[i] is the index of the closest element on its right such that its value is less than or equal to a[i].
• Once we have left and right arrays, we can calculate all the possible contiguous subarrays ending at each index i and take the maximum product subarray.

Algorithm:

• Initialize left to -1 and right to n for all indices.
• Initialize a stack to store indices.
• Iterate through the array a from left to right.
  • Pop from the stack while the top element of the stack has a value greater than or equal to the current element of a. Set right[top] to i-1.
  • Update left[i] as the index of the top element of the stack.
  • Push i onto the stack.
• Iterate through the stack from top to bottom. Pop from the stack and set right[top] to n-1.
• Initialize ans to 0.
• Iterate through the array a from left to right.
  • Calculate the product of the subarray a[left[i]+1:right[i]] and update ans if this product is greater than ans.
• Return ans.

Complexity Analysis:

• Time Complexity: O(n) as we are iterating through the array only once.
• Space Complexity: O(n) as we are using two arrays of size n and a stack of size n.

Code:

class Solution { public: int maxSumMinProduct(vector<int>& a) { int n = a.size(); vector<long long> left(n, -1); vector<long long> right(n, n); stack<long long> s; for(int i=0; i<n; ++i) { while(!s.empty() && a[s.top()]>=a[i]) { right[s.top()] = i-1; s.pop(); } left[i] = s.empty() ? -1 : s.top(); s.push(i); } while(!s.empty()) { right[s.top()] = n-1; s.pop(); } vector<long long> prefix(n, 0); prefix[0] = a[0]; for(int i=1; i<n; ++i) prefix[i] = prefix[i-1]+a[i]; long long ans = 0; for(int i=0; i<n; ++i) { long long sum = prefix[right[i]]-prefix[left[i]+1]+a[left[i]]; ans = max(ans, sum*a[i]); } return ans%1000000007; } };

1