Solution Explanation: Maximum Subarray Min-Product

This problem asks to find the maximum min-product of any non-empty subarray within a given array nums. The min-product of a subarray is defined as the minimum value in the subarray multiplied by the sum of the subarray's elements.

The optimal approach uses a monotonic stack along with prefix sums to efficiently solve this problem in linear time. Here's a breakdown:

1. Prefix Sum:

First, we calculate the prefix sum array s. s[i] represents the sum of all elements in nums from index 0 up to (and including) index i. This allows for quick calculation of the sum of any subarray: the sum of the subarray from index i to j (inclusive) is simply s[j+1] - s[i].

2. Monotonic Stack (for finding boundaries):

The core idea lies in efficiently finding, for each element nums[i], the leftmost and rightmost indices that bound the subarray where nums[i] is the minimum element. This is where the monotonic stack shines.

• Left Boundary (left[i]): A decreasing monotonic stack is used. As we iterate through nums, we pop elements from the stack that are greater than or equal to the current element. The top of the stack then represents the left boundary. If the stack is empty, the left boundary is -1.
• Right Boundary (right[i]): A similar approach is used, but with an increasing monotonic stack, iterating from right to left. This finds the right boundary where nums[i] is the minimum element. If the stack is empty, the right boundary is n (the length of the array).

3. Calculating Min-Products and Finding the Maximum:

Once we have the left and right boundaries for each element, we can calculate the min-product for each subarray where the element nums[i] is the minimum value within that subarray:

min_product[i] = nums[i] * (s[right[i]] - s[left[i] + 1])

Finally, we iterate through all min_product[i] and find the maximum value, which is the solution.

Time Complexity: O(n) - The algorithm iterates through the array nums a constant number of times (once for prefix sums, twice for the monotonic stack).

Space Complexity: O(n) - We use extra space for the left, right, and s arrays, which are all linear in size with respect to the input.

Code Explanation (Python):

class Solution:
    def maxSumMinProduct(self, nums: List[int]) -> int:
        n = len(nums)
        left = [-1] * n
        right = [n] * n
        stk = [] # Decreasing monotonic stack for left boundary
        for i, x in enumerate(nums):
            while stk and nums[stk[-1]] >= x:
                stk.pop()
            if stk:
                left[i] = stk[-1]
            stk.append(i)
 
        stk = [] # Increasing monotonic stack for right boundary
        for i in range(n - 1, -1, -1):
            while stk and nums[stk[-1]] > nums[i]:
                stk.pop()
            if stk:
                right[i] = stk[-1]
            stk.append(i)
 
        s = list(accumulate(nums, initial=0)) # Prefix sum
        mod = 10**9 + 7
        return max((s[right[i]] - s[left[i] + 1]) * x for i, x in enumerate(nums)) % mod

The code in other languages (Java, C++, Go, TypeScript) follows the same algorithmic approach, only differing in syntax and data structures. The key concepts of prefix sums and monotonic stacks remain consistent.