Compute Stock Profit with One or Unlimited Transactions
MetaSoftware Engineer · OnsiteLast updated
Compute maximum stock profit for both one transaction and unlimited nonoverlapping transactions in linear time, returning zero when no positive trade is available.
Problem
Given daily stock prices, return two values: the maximum profit when at most one buy-sell transaction is allowed, and the maximum profit when any number of non-overlapping transactions is allowed. You may hold at most one share at a time, and a sale must occur after its corresponding purchase.
Constraints & Assumptions
- The price list contains between 1 and 200,000 positive integers.
- Prices fit in 32-bit signed integers; use 64-bit arithmetic for total profit.
- Buying and selling on the same day adds no profit and is unnecessary.
- Return zero for a strategy that cannot make a positive profit.
Clarifications
- There are no fees, cooldown periods, or limits beyond the one-share holding rule.
- Unlimited transactions cannot overlap, but a new buy may follow an earlier sale.
- Return
[oneTransactionProfit, unlimitedTransactionsProfit].
Examples
prices = [7, 1, 5, 3, 6, 4]
output = [5, 7]
Hints
Hints
Hint 1
One transaction: Track the lowest price seen before each possible selling day.
Hint 2
Unlimited transactions: Identify every positive day-to-day increase that can be captured without overlapping holdings.
Solution walkthrough is for members
Get the full walkthrough with reference code and complexity analysis, plus Kitty Coach at 300 messages a day. Hints, the code runner and community answers stay free.