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

Hiring now

Cisco has 1,380 open roles right now

landed applies to roles like these for you, on each company’s own site, with answers written for the role.

Get 5x interviews10 free auto-applies. No card.

Executive Assistant, VP, Strategy & Standards (Hybrid)
San Jose, California, United States of America
Public Realtions Manager- Networking
Remote
Forward Deployed Engineer, Customer Experience AI
Krakow, Poland

Or practice this question first

Next question