Maximize Profit with One Stock Transaction
Company: Oracle
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
# Maximize Profit with One Stock Transaction
Implement `max_profit(prices)` for daily integer prices. Choose at most one buy followed by one later sell and return the maximum nonnegative profit. Return `0` when no profitable trade exists.
Constraints: up to `200000` prices; each price is an integer in `[0, 10^12]`. The returned profit is a signed 64-bit integer and is guaranteed not to exceed `2^53 - 1`, so all four language implementations represent it exactly. Aim for `O(n)` time and `O(1)` space.
```hint Respect transaction order
Test cases include a decreasing series and a low price that appears only after the best selling opportunity.
```
Quick Answer: Implement `max_profit(prices)` for daily integer prices. Work through the function contract, boundary cases, correctness argument, and time and space complexity expected in a production-quality solution.
Given daily integer stock prices, choose at most one buy followed by one sale on a later day. Return the maximum nonnegative profit, or zero when no profitable legal trade exists.
Constraints
- 0 <= len(prices) <= 200000.
- Every price is an integer from 0 through 10^12.
- At most one share is bought and sold, the sale day must be later, and the exact result is at most 2^53 - 1.
Examples
Input: ([],)
Expected Output: 0
Explanation: No day means no legal trade.
Input: ([7],)
Expected Output: 0
Explanation: A singleton cannot contain a later selling day.
Hints
- Check empty, singleton, flat, increasing, and decreasing price histories.
- Include a very low price that occurs only after an attractive earlier selling price.
- Exercise both allowed price boundaries and repeated equal best prices.