Leetcode 1856. Maximum Subarray Min-Product
Problem Explanation:
The problem asks to find the maximum min-product of any non-empty subarray of an array. The min-product of an array is the minimum value in the array multiplied by the array's sum. The answer should be returned as modulo 10^9 + 7. A subarray is defined as a contiguous part of an array.
Let's walk through an example:
Example: 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.
Solution Approach:
The solution to this problem can be achieved using a stack data structure. It based on the Monotonic Stack approach. The idea is to use a stack such that it maintains elements in increasing order, and we are able to find the nearest smaller element to the left and right for each element.
-
First, we initialize a stack data structure, a long integer variable 'ans' to store the result, and a 'prefix' vector to store the prefix sum of the given array (nums).
-
Then, we calculate the prefix sum of the array 'nums' and store it in the
prefix
vector. -
Next, we iterate through the array elements. For each element, we perform the following steps:
a. While the stack is not empty and the top element of the stack is greater than the current element, we:
- Pop the top element of the stack and store it in a variable
minVal
which contains the minimum value of the subarray. - Calculate the sum of the subarray using the
prefix
vector. - Update the answer (
ans
) by taking the maximum of its current value and the product ofminVal
andsum
.
b. Push the current index i onto the stack.
- Pop the top element of the stack and store it in a variable
-
Finally, return
ans
modulo 10^9 + 7.
Python Solution:
1class Solution:
2 def maxSumMinProduct(self, nums: List[int]) -> int:
3 kMod = 1_000_000_007
4 ans = 0
5 stack = []
6 prefix = [0] * (len(nums) + 1)
7
8 for i in range(len(nums)):
9 prefix[i + 1] = prefix[i] + nums[i]
10
11 for i in range(len(nums) + 1):
12 while stack and (i == len(nums) or nums[stack[-1]] > nums[i]):
13 minVal = nums[stack.pop()]
14 sum_ = prefix[i] if not stack else prefix[i] - prefix[stack[-1] + 1]
15 ans = max(ans, minVal * sum_)
16 stack.append(i)
17
18 return ans % kMod
Java Solution:
1import java.util.Stack;
2
3class Solution {
4
5 private static final int MOD = 1_000_000_007;
6
7 public int maxSumMinProduct(int[] nums) {
8 long ans = 0;
9 Stack<Integer> stack = new Stack<>();
10 long[] prefix = new long[nums.length + 1];
11
12 for (int i = 0; i < nums.length; ++i) {
13 prefix[i + 1] = prefix[i] + nums[i];
14 }
15
16 for (int i = 0; i <= nums.length; ++i) {
17 while (!stack.isEmpty() && (i == nums.length || nums[stack.peek()] > nums[i])) {
18 int minVal = nums[stack.pop()];
19 long sum = stack.isEmpty() ? prefix[i] : prefix[i] - prefix[stack.peek() + 1];
20 ans = Math.max(ans, minVal * sum);
21 }
22 stack.push(i);
23 }
24
25 return (int) (ans % MOD);
26 }
27}
JavaScript Solution:
1class Solution {
2 maxSumMinProduct(nums) {
3 const kMod = 1_000_000_007;
4 let ans = 0;
5 const stack = [];
6 const prefix = new Array(nums.length + 1).fill(0);
7
8 for (let i = 0; i < nums.length; ++i) {
9 prefix[i + 1] = prefix[i] + nums[i];
10 }
11
12 for (let i = 0; i <= nums.length; ++i) {
13 while (stack.length > 0 && (i === nums.length || nums[stack[stack.length - 1]] > nums[i])) {
14 const minVal = nums[stack.pop()];
15 const sum = stack.length === 0 ? prefix[i] : prefix[i] - prefix[stack[stack.length - 1] + 1];
16 ans = Math.max(ans, minVal * sum);
17 }
18 stack.push(i);
19 }
20
21 return ans % kMod;
22 }
23}
C++ Solution:
1#include <vector>
2#include <stack>
3
4class Solution {
5public:
6 int maxSumMinProduct(std::vector<int>& nums) {
7 const int kMod = 1'000'000'007;
8 long ans = 0;
9 std::stack<int> stack;
10 std::vector<long> prefix(nums.size() + 1);
11
12 for (int i = 0; i < nums.size(); ++i) {
13 prefix[i + 1] = prefix[i] + nums[i];
14 }
15
16 for (int i = 0; i <= nums.size(); ++i) {
17 while (!stack.empty() &&
18 (i == nums.size() || nums[stack.top()] > nums[i])) {
19 const int minVal = nums[stack.top()];
20 stack.pop();
21 const long sum =
22 stack.empty() ? prefix[i] : prefix[i] - prefix[stack.top() + 1];
23 ans = std::max(ans, minVal * sum);
24 }
25 stack.push(i);
26 }
27
28 return ans % kMod;
29 }
30};
C# Solution:
1using System;
2using System.Collections.Generic;
3
4public class Solution {
5 public int MaxSumMinProduct(int[] nums) {
6 const int kMod = 1_000_000_007;
7 long ans = 0;
8 Stack<int> stack = new Stack<int>();
9 long[] prefix = new long[nums.Length + 1];
10
11 for (int i = 0; i < nums.Length; ++i) {
12 prefix[i + 1] = prefix[i] + nums[i];
13 }
14
15 for (int i = 0; i <= nums.Length; ++i) {
16 while (stack.Count > 0 && (i == nums.Length || nums[stack.Peek()] > nums[i])) {
17 int minVal = nums[stack.Pop()];
18 long sum = stack.Count == 0 ? prefix[i] : prefix[i] - prefix[stack.Peek() + 1];
19 ans = Math.Max(ans, minVal * sum);
20 }
21 stack.Push(i);
22 }
23
24 return (int) (ans % kMod);
25 }
26}
27```In this article, we have explained the problem of finding the maximum min-product of any non-empty subarray of an array and discussed a solution approach based on Monotonic Stack. The solution implementation in Python, Java, JavaScript, C++, and C# languages has also been provided. By understanding this approach and analyzing the code implementation, one can have a clear understanding of how to solve this problem.
Got a question?ย Ask the Teaching Assistantย anything you don't understand.
Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.