Show problems as
Classic problem #1856MediumArrayStackMonotonic StackPrefix SumCartesian Tree

Maximum Subarray Min-Product

Real-world version: Weakest Link Times the Load
Tracked in this browser only
Read Maximum Subarray Min-Product on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

A run of couplings has strengths nums. For any contiguous stretch of it, the stretch's grade is the smallest strength in that stretch multiplied by the total of the strengths in it.

Return the largest grade over every non-empty contiguous stretch, modulo 10^9 + 7.

Examples

Example 1

Input
nums = [4, 11, 7, 2, 9, 6]
Output
126

The stretch 11, 7 has smallest strength 7 and totals 18, giving 126. Nothing beats it: reaching one further left drops the weakest link to 4, and reaching right drops it to 2. The best stretch on the other side, 9 and 6, only reaches 90.

Example 2

Input
nums = [1, 9, 9, 9, 1]
Output
243

The three nines in the middle have smallest strength 9 and total 27, giving 243. Reaching out to either 1 would cut the weakest link to 1.

Example 3

Input
nums = [1000000, 1000000, 1000000, 1000000]
Output
999972007

The whole run is the best stretch, and its grade is a million times four million, which leaves this remainder once reduced.

Constraints

  • 1 <= nums.length <= 10^5
  • 1 <= nums[i] <= 10^6

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def max_sum_min_product(nums: list[int]) -> int:
Java
public int maxSumMinProduct(int[] nums)

More on the same topics