MAXIMUM SUBARRAY MIN PRODUCT LEETCODE | FULL EXPLANATION

In this video, I have discussed the 1856th Problem of Leetcode that is
MAXIMUM SUBARRAY MIN PRODUCT

The min-product of an array is equal to the minimum value in the array multiplied by the array's sum.

For example, the array [3,2,5] (minimum value is 2) has a min-product of 2 * (3+2+5) = 2 * 10 = 20.
Given an array of integers nums, return the maximum min-product of any non-empty subarray of nums. Since the answer may be large, return it modulo 109 + 7.

Note that the min-product should be maximized before performing the modulo operation. Testcases are generated such that the maximum min-product without modulo will fit in a 64-bit signed integer.

A subarray is a contiguous part of an array.



Example 1:

Input: nums = [1,2,3,2]
Output: 14
Explanation: The maximum min-product is achieved with the subarray [2,3,2] (minimum value is 2).
2 * (2+3+2) = 2 * 7 = 14.

[saisupreeth]

It took me time to understand, but overall I learned different approach to solve this problem. Thanks!!

[letscode-it]

Can we find the next and previous smaller by simple traversal without stack??

[laaiba]

Sir you've changed your look, looking cool sir... big fan 🙌🏼

[samudralaswathi]

I think it's better to explain with code

[SaurabhJeena-shgh]

done by myself no hints


class Solution {
public int maxSumMinProduct(int[] nums) {
long max=Long.MIN_VALUE;
Stack<Integer> stack=new Stack<>();
long [] prefixSum=new long [nums.length];
int [] ns=new int [nums.length];
int [] ps=new int [nums.length];
long sum=0;
for(int i=0;i<nums.length;i++){
sum=sum+nums[i];
prefixSum[i]=sum;
}
for(int i=ns.length-1;i>=0;i--){

stack.pop();

}
if(stack.isEmpty()){
ns[i]=nums.length;
}
else{
ns[i]=stack.peek();
}
stack.push(i);
}
stack.clear();
for(int i=0;i<nums.length;i++){

stack.pop();

}
if(stack.isEmpty()){
ps[i]=-1;
}
else{
ps[i]=stack.peek();
}
stack.push(i);
}
for(int i=0;i<nums.length;i++){
long leftsum;
if(ps[i]==-1){
leftsum=0;


}
else{
leftsum=prefixSum[ps[i]];
}
long rightsum=prefixSum[ns[i]-1];
long
max=Math.max(max, maxMinProd);

}
int
return(int) (max%mod);


}
}