Best Time to Buy and Sell Stock IV

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 k and an array prices, where prices[i] is the price of a given stock on day i. Your goal is to maximize the total profit you can earn by completing **at most** k transactions. A single transaction consists of buying the stock on one day and later selling it on a strictly later day. You may not hold more than one share of the stock at a time, which means you must sell the share you are holding before you can buy again. You also cannot buy and sell on the same day. Return the maximum profit achievable. If no profitable sequence of transactions exists, return 0 (you may simply choose to make no transactions).

Examples

Input: k = 2, prices = [2, 4, 1]
Output: 2
Buy on day 0 (price 2) and sell on day 1 (price 4) for a profit of 4 - 2 = 2. A second transaction would only reduce profit, so one transaction is optimal.
Input: k = 2, prices = [3, 2, 6, 5, 0, 3]
Output: 7
Buy on day 1 (price 2) and sell on day 2 (price 6) for a profit of 4, then buy on day 4 (price 0) and sell on day 5 (price 3) for a profit of 3. Total profit = 4 + 3 = 7.
Input: k = 1, prices = [7, 6, 4, 3, 1]
Output: 0
Prices only fall, so any transaction would lose money. The best choice is to make no transaction, yielding a profit of 0.

Constraints

  • `0 <= k <= 100`
  • `0 <= prices.length <= 1000`
  • `0 <= prices[i] <= 1000`

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