Coding

Best time to buy and sell stock IV

Asked at

Cisco

Goldman Sachs

Informatica

Meta

1Give yourself 5 minutes

2Answer out loud, not in your head

3Then compare with the answer below

The problem

Given an array, arr, of n integers, where arr[i] represents the price of the stock on an ith day, determine the** maximum profit** achievable by completing at most k transactions in total. Holding** at most **one share of the stock at any given time is allowed, meaning buying and selling the stock k times is permitted, but the stock must be sold before buying it again. Buying and selling the stock on the same day is allowed.

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

Input: arr = [1, 2, 4, 2, 5, 7, 2, 4, 9, 0], k = 3 Output: 15 Explanation: Buy on day 1 (price = 1) and sell on day 3 (price = 4), profit = 4 - 1 = 3. Then buy on day 4 (price = 2) and sell on day 6 (price = 7), profit = 7 - 2 = 5. Then buy on day 7 (price = 2) and sell on day 9 (price = 9), profit = 9 - 2 = 7. Total profit is 3 + 5 + 7 = 15.

Input: arr = [1, 3, 2, 8, 4, 9], k = 2

1 <= n<= 103
0 <= arr[i] <= 104
0 <= k <= 100

cpp

class Solution{
public:
    int stockBuySell(vector<int> arr, int n, int k){
  
    }
};

java

class Solution {
    public int stockBuySell(int[] arr, int n, int k) {
       
    }
}

python

class Solution:
    def stockBuySell(self, arr, n, k):

javascript

class Solution {
    stockBuySell(arr, n, k) {
    
    }
}

csharp

class Solution
{
    public int StockBuySell(int[] arr, int n, int k)
    {
       
    }
}

func stockBuySell(arr []int, n int, k int) int {

}

Stuck? Show a way to structure it+

01Handle k = 0 and use the unlimited-transactions shortcut when k is at least n / 2.
02For each transaction count, track the best profit while holding and after selling.
03On each price, choose whether to keep each state or perform its buy or sell transition.
04Return the best not-holding state after at most k completed transactions.

Reference answer

A transaction is completed by a sell, and only one share may be held. Use two states for each transaction count t: buy[t] is the best profit while holding a share after starting transaction t, and sell[t] is the best profit after completing at most t sells. Initialize buys to negative infinity and sell[0] = 0.

For each price and each t from 1 through k, update buy[t] = max(buy[t], sell[t-1] - price) and sell[t] = max(sell[t], buy[t] + price). Using copied previous-day arrays is the clearest formulation; careful in-place ordering is also possible. The result is sell[k], with unused transactions allowed.

When k >= n / 2, the transaction limit cannot bind because at most one profitable buy-sell pair can be completed every two days. In that case, sum every positive day-to-day increase in O(n) time. Otherwise the DP takes O(nk) time and O(k) space. This formulation handles k = 0, declining prices, and buying and selling at the same price without special cases.

Then expect these follow-ups

Why does k >= n / 2 reduce to the unlimited-transactions problem?
Tests: complexity optimization
How would a transaction fee or cooldown change the states?
Tests: DP adaptation

Free to read · better with Enzo

Practice this out loud with Enzo

Enzo runs it as a mock interview, pushes back with follow-ups, and grades you on the rubric.

Continue with Enzo Sign up free

Next question