Maximum Profit with Unlimited Stock Transactions
Company: Point72
Role: Quantitative Researcher
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
# 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
```text
prices = [7, 1, 5, 3, 6, 4]
output = 7
```
```text
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.
```
Overview: Given daily stock prices, compute the maximum profit from any number of buy-and-sell transactions. Work through the function contract, boundary cases, correctness argument, and time and space complexity expected in a production-quality solution.
Read the full Point72 Quantitative Researcher interview experience this question came from
Given daily stock prices, return the maximum profit obtainable from any number of buy-and-sell transactions. You may hold at most one share, must sell before buying again, and receive no extra profit by buying and selling at the same price on one day. There are no fees or cooldown periods.
Constraints
- 0 <= len(prices) <= 200000.
- 0 <= prices[i] <= 10^9 for every day.
- At most one share may be held, every sale follows a buy, and there are no fees or cooldowns; the result fits signed 64-bit range.
Examples
Input: ([],)
Expected Output: 0
Explanation: No trading day permits no transaction.
Input: ([5],)
Expected Output: 0
Explanation: A single price cannot form a profitable transaction.
Hints
- Compare empty, single-day, flat, strictly rising, and strictly falling price histories.
- Include several separated rises with declines between them and verify that every transaction remains legal.
- Use repeated full-range rises to exercise a result larger than a single price value.