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.

1. 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).

2. Then, we calculate the prefix sum of the array 'nums' and store it in the prefix vector.

3. 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 of minVal and sum.

   b. Push the current index i onto the stack.

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