1041. Take Every Rise

Prices are given for n consecutive days. You may buy and sell as many times as you like, but you may hold at most one unit at a time, and you must sell before you buy again. Buying and selling on the same day is not allowed.

Print the largest total profit.

7 1 5 3 6 4 -> 7 buy at 1 sell at 5, buy at 3 sell at 6 1 2 3 4 5 -> 4 buy at 1, sell at 5 7 6 4 3 1 -> 0 never trade 1 4 2 5 3 6 1 -> 9

## What most people try first

Look for the peaks and the valleys, pair each valley with the peak after it, and add up the differences. That is correct, and it is fiddly: a plateau in the middle of a rise is neither a peak nor a valley, and the last day may be a peak with no closing rule.

The other instinct is a table over (day, holding or not), which is also correct and is what problems #406, #443 and #469 do when a cost or a cap makes the choice interesting. Here there is no cost and no cap, and the table carries no information the prices do not already hold.

## Take every rise

profit = 0 for i in 1 .. n-1: if price[i] > price[i-1]: profit += price[i] - price[i-1]

On 7 1 5 3 6 4 the rises are 1 -> 5 worth 4 and 3 -> 6 worth 3, so 7.

## Why that equals the optimum, in both directions

It is an UPPER BOUND. Take any legal set of trades. A trade buying on day b and selling on day s earns price[s] - price[b], which telescopes:

price[s] - price[b] = (price[b+1] - price[b]) + (price[b+2] - price[b+1]) + ... + (price[s] - price[s-1])

so every trade's profit is a sum of consecutive day-to-day steps, and those steps may be negative. Trades never overlap, so no step is counted twice. Therefore any set of trades earns at most the sum of all the POSITIVE steps, which is what the rule collects.

It is ACHIEVABLE. Buy the day before every rise and sell at the end of it. Each maximal run of increases becomes one real trade; a run of length k gives one buy, one sell, and exactly the sum of its k steps. The trades sit inside disjoint runs, so they never overlap and no day is used twice.

Upper bound plus achievable is the whole proof, and this two-sided shape is worth recognising: it is how most counting greedies are justified.

## The comparison that must be strict

price[i] > price[i-1], not >=. A flat day contributes zero either way, so the answer is unchanged, but a >= written as part of a peak-and-valley version does change the answer by producing a buy and a sell on the same price. Here it is harmless; in #443, where every trade pays a fee, the same slip loses money on every plateau.

## Overflow

n reaches 200000 and a price reaches 10^9, so an alternating input such as 0 10^9 0 10^9 ... earns close to 10^14. That does not fit in a signed 32 bit integer, whose limit is 2147483647. The running total must be 64 bit. A single difference does fit, so the bug shows only after a few rises, which is why the short test with three rises of a billion is in the list.

## Where this sits

Problem #406 allows ONE trade and is a different question: there the answer is the best single pair, and taking every rise would overcount. #443 charges a fee per trade, which destroys this argument entirely, because splitting a long rise into two trades now costs money.

## Cost

Time O(n). Space O(1) beyond the input.

Constraints - `1 ≤ n ≤ 200000` - `0 ≤ price[i] ≤ 1000000000`