Katkat

Compute Stock Profit with One or Unlimited Transactions

MetaSoftware Engineer · Onsite

Last 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.