Katkat
Back

Maximize Profit with at Most K Transactions

TekionSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

This problem tests dynamic programming optimization by finding the maximum profit from stock trading with a constraint on the total number of allowed transactions.

Maximize Profit with K Transactions

You are given an array of integers prices where prices[i] represents the price of a given stock on the i-th day, and an integer k representing the maximum number of transactions you are allowed to make.

A transaction consists of buying and then selling one share of the stock. You may not engage in multiple transactions simultaneously (i.e., you must sell the stock before you buy again).

Write a function maxProfit(k, prices) that returns the maximum profit you can achieve.

Constraints

  • 0 <= prices.length <= 10^3
  • 0 <= k <= 100
  • 0 <= prices[i] <= 1000

Examples

Example 1: Input: k = 2, prices = [2, 4, 1] Output: 2 Explanation: Buy on day 1 (price = 2) and sell on day 2 (price = 4). Profit = 4 - 2 = 2.

Example 2: Input: k = 2, prices = [3, 2, 6, 5, 0, 3] Output: 7 Explanation: Buy on day 2 (price = 2) and sell on day 3 (price = 6), profit = 4. Then buy on day 5 (price = 0) and sell on day 6 (price = 3), profit = 3. Total profit = 4 + 3 = 7.

Edge Cases

  • If k is very large (e.g., k >= prices.length / 2), the problem becomes the same as making as many transactions as you want.
  • If the input array is empty or k is 0, the profit is 0.

Hints

Hint 1

Define a 2D DP table `dp[i][j]` representing the max profit using at most `i` transactions up to day `j`.

Hint 2

The recurrence relation involves either not making a trade on day `j` or selling a stock bought on some previous day `m`.

Hint 3

Optimize the space complexity by observing that the current transaction state only depends on the previous transaction state.

Follow-up questions

  • How would you optimize the algorithm if the number of transactions `k` is significantly larger than the number of days?
  • What is the space complexity of your solution, and can it be reduced to O(n)?
  • How would the logic change if there was a 'cooldown' period of one day after selling a stock before you could buy again?