FastPrepStock Profit with a Transaction Limit

Stock Profit with a Transaction Limit

Citadel logoCitadel● HardNEW GRADPHONE SCREEN

Updated

Problem statement

You are given an array prices, where prices[i] is the price of one share on day i, and a nonnegative integer k.

Return the largest total profit from at most k completed buy-and-sell transactions. Hold at most one share at a time. Buy before selling that share, and sell before starting another transaction. You may choose to make no trades.

Progressive versions

  • With k = 1, solve the single-transaction version in one pass.
  • When the transaction limit cannot restrict the answer, solve the unlimited-transactions version.
  • Handle a general transaction limit and explain how to reduce the memory used by dynamic programming.

There are no transaction fees or cooldown days. A buy and its sale must occur on different days.

Function

maxStockProfit(prices: int[], k: int) → int

Examples

Example 1

prices = [3,2,6,5,0,3]k = 2return = 7

Buy at 2 and sell at 6 for a profit of 4. Then buy at 0 and sell at 3 for a profit of 3. The total profit is 7.

Example 2

prices = [7,1,5,3,6,4]k = 1return = 5

Buy at 1 and sell at 6. Their difference is 5, which is the largest profit from one transaction.

Example 3

prices = [1,3,2,5]k = 2000return = 5

Take the rise from 1 to 3 and the rise from 2 to 5. These two transactions earn 2 + 3 = 5.

Constraints

  • 0 <= prices.length <= 2000.
  • 0 <= prices[i] <= 10^6.
  • 0 <= k <= 2000.

More Citadel Phone Screen questions

Similar questions at other companies

Interview reports that mention this question

Citadel interview experiences

All Citadel interview questionsSee Citadel hiring insights
Saved
class Solution {
    public int maxStockProfit(int[] prices, int k) {
        // Write your code here.
    }
}
Checking account…