855. The Best Minimum Times Sum

Read n positive values. The SCORE of a contiguous stretch is its smallest value multiplied by the total of all its values. Print the largest score over all stretches, modulo 1000000007.

The maximum is found over the exact scores first, and only the winner is reduced.

1 2 3 2 -> 14 2 3 3 1 -> 18 1 1 1 1 1 -> 5

For 1 2 3 2 the best stretch is 2 3 2, whose minimum is 2 and whose total is 7, giving 14. The whole row scores only 1 * 8 = 8.

## The first thing to notice

All values are positive, so extending a stretch never lowers its total. That means: for a stretch whose minimum is at position i, the best possible partner is the WIDEST stretch in which i is still the minimum. Growing beyond that boundary would lower the minimum, which is not obviously bad, but that wider stretch is then counted under a different i anyway.

So it is enough to consider one candidate per position:

score(i) = a[i] * ( sum of a over the widest stretch whose minimum is a[i] )

and take the maximum over i.

## Why that really covers every stretch

Take any stretch [l, r] and let i be a position holding its minimum. Then [l, r] is inside the widest stretch for i, and since all values are positive the wider one has a total at least as large, with the same minimum. So no stretch beats the candidate list. Every candidate is itself a real stretch, so the maximum over candidates is exactly the answer.

This is the step that fails if values may be negative or zero, which is why the constraint is there and why it is worth noticing.

## The widest stretch, and which comparison to use

The widest stretch in which a[i] is a minimum runs between the nearest STRICTLY smaller values on each side:

lo = previousStrictlySmaller(i) + 1 hi = nextStrictlySmaller(i) - 1

Both boundaries strict, because an equal value does not lower the minimum. That is the same convention as problem 838 and the OPPOSITE of the counting problems, where one side must be loose to avoid double counting. Here nothing is being counted, only maximised, so double covering a stretch is harmless and the honest widest window is what is wanted.

Two stacks kept increasing in value give both boundaries in O(n).

## Getting the totals

A prefix sum array turns the total of [lo, hi] into pre[hi+1] - pre[lo] in constant time. Build it once, in 64-bit values, because the whole row sums to 10^11.

## Where it overflows

The product is at most 10^6 * 10^11 = 10^17, which fits in a signed 64-bit integer but not in a 32-bit one. Reduce ONLY at the end, after the maximum has been chosen: reducing earlier compares remainders instead of scores and picks the wrong stretch.

## Related problems

Problem 838 computes these same widest stretches, and problem 862 maximises a similar product but restricts the stretch to those covering one given position.

## Cost

Time O(n), two stack passes plus one prefix sum. Space O(n).

Constraints - `1 ≤ n ≤ 100000` - `1 ≤ a[i] ≤ 10^6` - the exact maximum can reach `10^17`, so it needs 64 bits before the remainder