Maximize the Product of the Subarray Sum with its Minimum Element

Optimized Approach

Declare a presum array to store prefix sum.

⬇

Declare two arrays, l[] and r[] to store index of nearest smaller elements on left and right respectively.

⬇

Declare a stack.

⬇

Find all left index.

⬇

Reset stack.

⬇

Find all right index.

⬇

Iterate over the range and Calculate the product.

⬇

Update the maximum product and return.

.

Till now, I guess you must have got the basic idea of what has been asked in the problem statement. So, I strongly recommend you first give it a try and solve some more related problems.

Coding Ninjas Studio.

PseudoCode

Algorithm

___________________________________________________________________

procedure maxValue( a[], n ):

___________________________________________________________________

1.   int presum[n]

2.   For i=1 to n: presum[i] = presum[i - 1] + a[i]

3.   stack<int> st 

4.   Begin loop and iterate from 1 to n.

   while (!st.empty() && a[st.top()] >= a[i]): st.pop()

   if (!st.empty()): l[i] = st.top() + 1

   Else l[i] = 0

  st.push(i)

      End loop.

5.  while(!st.empty()): st.pop()

6.  Begin loop and iterate from n-1 to 0

while (!st.empty() && a[st.top()] >= a[i]): st.pop()

 if (!st.empty()): r[i] = st.top() - 1

     Else: r[i] = n - 1

           st.push(i);

      End loop.

7.  maxProduct = 0

8.  Iterate over the range [0, n)

9.  tempProduct = a[i] * (presum[r[i]] - (l[i] == 0 ? 0 : presum[l[i] - 1]));

10.maxProduct = max(maxProduct, tempProduct);

11. Return maxproduct.

12. end procedure

___________________________________________________________________

Implementation in C++

// Maximize the product of the subarray sum with its minimum element
#include<bits/stdc++.h>
using namespace std;
 
// Function to find the maximum product possible
void maxValue(int a[], int n)
{
     
    // Stores prefix sum
    int presum[n];
 
    presum[0] = a[0];
 
    // Find the prefix sum array
    for(int i = 1; i < n; i++)
    {
        presum[i] = presum[i - 1] + a[i];
    }
 
    // l[] and r[] stores index of nearest smaller elements on left and right respectively
    int l[n], r[n];
 
    stack<int> st;
 
    // Find all left index
    for(int i = 1; i < n; i++)
    {
         
        // Until stack is non-empty & top element is greater than the current element
        while (!st.empty() && a[st.top()] >= a[i])
            st.pop();
 
        // If stack is empty
        if (!st.empty())
            l[i] = st.top() + 1;
        else
            l[i] = 0;
 
        // Push the current index i
        st.push(i);
    }
 
    // Reset stack
    while(!st.empty())
    st.pop();
 
    // Find all right index
    for(int i = n - 1; i >= 0; i--)
    {
         
        // Until stack is non-empty & top element is greater than the current element
        while (!st.empty() && a[st.top()] >= a[i])
            st.pop();
 
            if (!st.empty())
                r[i] = st.top() - 1;
            else
                r[i] = n - 1;
 
        // Push the current index i
        st.push(i);
    }
 
    // Stores the maximum product
    int maxProduct = 0;
 
    int tempProduct;
 
    // Iterate over the range [0, n)
    for(int i = 0; i < n; i++)
    {
         
        // Calculate the product
        tempProduct = a[i] * (presum[r[i]] - (l[i] == 0 ? 0 : presum[l[i] - 1]));
 
        // Update the maximum product
        maxProduct = max(maxProduct, tempProduct);
    }
 
    // Return the maximum product
    cout << maxProduct;
}

int main()
{
    
    int n = 6;
    int arr[] = { 3, 1, 6, 4, 5, 2 };
 
    
    maxValue(arr, n);
}

 

Output:

Input: 
6
3 1 6 4 5 2
Output:
60

 

Complexity Analysis

Time Complexity: O(n)

The above algorithm takes O(n) time complexity, where n is the size of the array. We traverse the array only once.

Space complexity: The space complexity is O(n), as we are only introducing an array for storing the position of elements. 

Check out this problem - First And Last Occurrences Of X

Frequently Asked Questions

What is prefix sum?

Prefix sum is a sum of all elements before the current element including the current element.

Is there any Prerequisite for this problem? 

Yes, you must understand the working of the stack. Then this problem would seem easy.

How to understand that a problem can be optimized using a stack?

If two loops are used, and our j loop depends on i, a stack must be used in such a problem.

Conclusion

This article taught us to Maximize the product of the subarray sum with its minimum element by approaching the problem using a stack. We discussed its implementation using illustrations, pseudocode, and then proper code.

We hope you could take away critical techniques like analyzing problems by walking over the execution of the examples and finding out the recursive pattern followed in most stack problems.

Now, we recommend you practice problem sets based on stacks to master your fundamentals. You can get a wide range of questions similar to this problem on Coding Ninjas Studio. 

Recommended Problems:

• Sum of Minimum and Maximum Elements of all Subarrays of size K
• Maximum Product Subarray

Recommended Reading:

• Count Subarray for every array element in which they are minimum
• Count Array elements having at least one smaller element on its left and right-hand side

Do check out The Interview guide for Product Based Companies as well as some of the Popular Interview Problems from Top companies like Amazon, Adobe, Google, Uber, Microsoft, etc. on Coding Ninjas Studio.

Also check out some of the Guided Paths on topics such as Data Structure and Algorithms, Competitive Programming, Operating Systems, Computer Networks, DBMS, System Design, Basics of C++, Basics of Java, Basics of Python, etc. as well as some Contests, Test Series, Interview Bundles, and some Interview Experiences curated by top Industry Experts only on Coding Ninjas Studio.

Happy Coding.