Maximum Profit with Unlimited Stock Transactions

Given daily stock prices, compute the maximum profit from any number of buy-and-sell transactions. You may hold at most one share at a time, must sell before buying again, and may buy and sell on the same day only for zero additional profit.

Function Contract

Implement max_profit(prices) -> int.

Constraints

• 0 <= number of days <= 200000.
• 0 <= each price <= 10^9.
• No transaction fees or cooldown periods apply.
• The result fits in a signed 64-bit integer.

Examples

prices = [7, 1, 5, 3, 6, 4]
output = 7

prices = [7, 6, 4, 3, 1]
output = 0

Hint: Check monotone inputs

Compare strictly rising, strictly falling, flat, and single-day price sequences.

Hint: Enforce transaction legality

Verify that a proposed profit never depends on holding more than one share or selling before a share is owned.

Maximum Profit with Unlimited Stock Transactions

Hints

1. Compare empty, single-day, flat, strictly rising, and strictly falling price histories.
2. Include several separated rises with declines between them and verify that every transaction remains legal.
3. Use repeated full-range rises to exercise a result larger than a single price value.

Approach

Any increasing run from a valley to a peak has profit equal to the sum of its positive day-to-day changes. Capturing every positive adjacent change is therefore equivalent to buying at each valley and selling at each following peak, while never holding more than one share. Negative and zero changes contribute nothing.

• Time complexity: O(n) for n daily prices.
• Space complexity: O(1) auxiliary space.