Best Time to Buy and Sell Stock III

HardDynamic Programmingstate machine DP

Solve this the way you would in the interview: out loud, on a timer, with an AI interviewer asking follow-ups while you code. You get a scored report at the end.

Practice this as a mock interviewFree to start, no account needed

Problem

You are given an integer array prices where prices[i] is the price of a single stock on day i. Your goal is to maximize the profit you can earn by completing **at most two** buy/sell transactions. A transaction consists of buying one share of the stock and later selling that same share. There is one important restriction: you may not hold more than one share at a time. In other words, you must sell the stock you currently own **before** you are allowed to buy again. Buying and selling on the same day is not useful since it yields zero profit. Return the **maximum total profit** you can achieve. If no profitable sequence of transactions exists, return 0.

Examples

Input: prices = [3,3,5,0,0,3,1,4]
Output: 6
Buy on day 4 (price = 0) and sell on day 6 (price = 3) for profit 3, then buy on day 7 (price = 1) and sell on day 8 (price = 4) for profit 3. Total = 6.
Input: prices = [1,2,3,4,5]
Output: 4
Buy on day 1 (price = 1) and sell on day 5 (price = 5) for profit 4. A second transaction would only reduce the total, so one transaction is best.
Input: prices = [7,6,4,3,1]
Output: 0
Prices only fall, so no transaction can be profitable. The best choice is to make no transactions at all.

Constraints

  • 1 <= prices.length <= 10^5
  • 0 <= prices[i] <= 10^5
  • At most two transactions are allowed.
  • You cannot hold more than one share at any moment (sell before buying again).

What the interviewer grades

A correct solution is one of five scores. The report also grades problem understanding (did you clarify inputs and edge cases before coding), problem solving, communication while you work, code quality, and testing. See a sample report, or read up on the pattern in the lessons.

More state machine DP problems