692. The Heaviest Stretch With No Repeated Value
Find the CONTIGUOUS stretch whose values are all DIFFERENT and whose total is as large as possible. Print that total.
4 2 4 5 6 -> 17 the stretch 4 5 6
5 2 1 2 5 2 1 2 5 -> 8 the stretch 5 2 1
1 1 1 -> 1
## Two things travel with the window
A set recording which values are inside, and a running total. Both must be updated on every entry and every exit, and forgetting one of them is the usual bug.
for hi in 0 .. n-1:
while a[hi] is already in the set:
remove a[lo] from the set; total -= a[lo]; lo += 1
add a[hi]; total += a[hi]
best = max(best, total)
## Why the shrink loop is a while, not an if
When the repeat of a[hi] sits deep inside the window, everything up to and including its
earlier copy must leave. That can be many elements, so the left edge may jump several places in
one step.
An if removes only one and leaves the duplicate inside, and the set then rejects the new
value forever. 5 2 1 2 5 2 1 2 5 is the input that exposes it, because the repeats are
frequent and deep.
## Why the maximum is taken after adding
The window is only guaranteed duplicate-free once the shrink loop has finished and the new value is in. Recording the best before that would measure an invalid or incomplete window.
That ordering, shrink then add then record, is the standard shape for a grow-shrink window and it is worth fixing in the hand.
## Contrast with problem 687
687 lets a value appear up to k times and wants the longest window. Set k = 1 there and
the invariant becomes exactly this one, no repeats at all. What changes here is the quantity
being maximised: the heaviest window rather than the longest.
Those are genuinely different answers, and the difference is not cosmetic. In
1 2 3 4 3 100 the longest duplicate-free window is 1 2 3 4, four values totalling 10,
while the heaviest is 4 3 100, three values totalling 107. A solution that tracks the
longest window and reports its sum gets 10.
Most of this topic is that observation repeated.
## Boundaries
All values equal gives a single element. All values distinct gives the whole array.
## Overflow
200000 values of up to 10^4 total exactly 2 * 10^9. The move here is to check that
figure against the limit rather than to recognise the shape: a signed 32 bit integer holds
up to 2147483647, so 2000000000 FITS, with about seven percent to spare. This problem
has no overflow, and a 64 bit accumulator buys margin rather than correctness.
The margin is thin enough to be worth the arithmetic. Raise the value cap to 10^5 and the
total becomes 2 * 10^10; raise the length cap to 10^6 and it becomes 10^10. Either
one is an order of magnitude past what 32 bits holds.
## Cost
Time O(n). Space O(n) for the set.
Constraints - `1 ≤ n ≤ 200000` - `1 ≤ each value ≤ 10^4`
Input
The first line contains an integer n.
The second line contains n positive integers.
Output
Print one integer, the largest total of a stretch with no repeated value.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.