Maximize the product of the subarray sum with its minimum element

Urwashi Priya
Last Updated: May 13, 2022

Introduction

In this blog, we will discuss a stack problem that has been asked frequently in Interviews and also is one of the most critical sets of stack algorithms.

Problem statement

The problem is to Maximize the product of the subarray sum with its minimum element.

Revisiting stack

Before we proceed, we must know what a Stack is?

A Stack is a linear data structure that stores a list of items, which can be added to or removed from the list only at one end. It is based on LIFO (Last in First Out) mechanism. Stack has four operations: Push, Pop, top, empty.

Now let’s look at the problem.

We need to Maximize the product of the subarray sum with its minimum element. This means we have to find the subarray sum and maximise its product by multiplying with the minimum element of the subarray.

Sample Example

For example: say we are given an array: 3,1,6,4,5,2.
Maximum product possible according to given problem statement=60.

It can be calculated as: (6+4+5)*4=60

Naive Approach

First, I will be discussing the brute force approach to Maximize the product of the subarray sum with its minimum element:

Generate all possible subarrays.

Find the sum of the subarray and multiply the sum by the smallest element of the subarray.

Repeat the above step for each subarray. 

Find the maximum product and print it.

 

But this approach will take O(n³) time, so now discussing the optimised approach, i.e. Stack Approach, to Maximize the product of the subarray sum with its minimum element.

Optimised 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.

codestudio.

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.

12end 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: O(n), as we are only introducing an array for storing the position of elements. 

Frequently Asked Questions

  1. What is prefix sum?
    Answer) Prefix sum is a sum of all elements before the current element including the current element.
     
  2. Is there any Prerequisite for this problem? 
    Answer)Yes, you must understand the working of the stack. Then this problem would seem easy.
     
  3. How to understand that a problem can be optimised using a stack?
    Answer)If two loops are used, and our j loop depends on i, stack must be used in such a problem.

Key Takeaways

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 analysing 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 CodeStudio

It's not the end. Must solve the problem of similar types. 

Happy Coding.

Was this article helpful ?
0 upvotes