Best Time - Unlimited Transactions

🎯

Best Time - Unlimited Transactions

mediumDPAmazonFacebookGoogle

Imagine you are a stock trader who can buy and sell a stock any number of times to maximize profit. How do you decide when to buy and sell to get the best total profit?

💡 This problem is a classic example of dynamic programming applied to stock trading. Beginners often struggle because the problem looks like it could be solved greedily, but the unlimited transactions and timing constraints require careful state management to avoid missing optimal profits.

📋

Problem Statement

Given an array prices where prices[i] is the price of a given stock on the i-th day, find the maximum profit you can achieve. You may complete as many transactions as you like (i.e., buy one and sell one share of the stock multiple times). However, you must sell the stock before you buy again.

1 ≤ prices.length ≤ 10^50 ≤ prices[i] ≤ 10^4

💡

Example

Input"[7,1,5,3,6,4]"

Output7

Buy on day 2 (price=1) and sell on day 3 (price=5), profit = 4. Then buy on day 4 (price=3) and sell on day 5 (price=6), profit = 3. Total profit = 4 + 3 = 7.

Input"[1,2,3,4,5]"

Output4

Buy on day 1 and sell on day 5 for a profit of 4. Alternatively, buy and sell every day for the same total profit.

Input"[7,6,4,3,1]"

Output0

No transactions are done, so the max profit is 0.

• prices with all equal values → expected output 0
• prices with strictly decreasing values → expected output 0
• prices with strictly increasing values → expected output prices[n-1] - prices[0]
• prices with single day → expected output 0

🔁

Why DP?

Why greedy fails:

A naive greedy approach might try to buy at the lowest price and sell at the highest price once, but this misses multiple profitable transactions. For example, prices = [1,2,3,0,2], greedy buy low once misses the profit from the second rise.

DP state:

dp[i][0] = max profit on day i holding no stock; dp[i][1] = max profit on day i holding one stock.

Recurrence:dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i]) dp[i][1] = max(dp[i-1][1], dp[i-1][0] - prices[i])

On day i, if not holding stock, either we did nothing or sold stock today; if holding stock, either we did nothing or bought stock today.

⚠️

Common Mistakes

Trying to buy and sell on the same day

Leads to incorrect profit calculation or double counting

✅ Ensure sell happens before buy on the next day or track states properly

Not handling the initial holding state correctly

Incorrect initialization leads to wrong profits

✅ Initialize holding state as -prices[0] to represent buying on day 0

Using greedy approach summing only positive differences

Fails on some inputs where multiple transactions are better

✅ Use DP to track states instead of simple greedy

Not memoizing recursive calls

Leads to exponential time and TLE

✅ Use memoization or tabulation to cache results

Confusing holding and not holding states in DP

Leads to incorrect transitions and wrong answers

✅ Clearly define and track states separately

🧠

Brute Force (Pure Recursion)

💡 Starting with brute force helps understand the problem's decision tree and why naive recursion is inefficient due to repeated calculations.

Intuition

Try all possible buy/sell decisions on each day recursively, tracking whether you currently hold a stock or not.

Algorithm

1. Define a recursive function with parameters: current day and holding state.
2. If at last day, return 0 profit.
3. If holding stock, choose to sell or hold.
4. If not holding, choose to buy or skip.
5. Return the max profit from these choices.

💡 The recursion explores all buy/sell combinations, which is conceptually simple but computationally expensive.

Recurrence:f(i, holding) = max( if holding: max(f(i+1, holding), f(i+1, not holding) + prices[i]), else: max(f(i+1, not holding), f(i+1, holding) - prices[i]) )

</>

Code

def maxProfit(prices):
    n = len(prices)
    def dfs(i, holding):
        if i == n:
            return 0
        if holding:
            sell = dfs(i+1, False) + prices[i]
            hold = dfs(i+1, True)
            return max(sell, hold)
        else:
            buy = dfs(i+1, True) - prices[i]
            skip = dfs(i+1, False)
            return max(buy, skip)
    return dfs(0, False)

# Example usage
if __name__ == '__main__':
    print(maxProfit([7,1,5,3,6,4]))  # Output: 7

Line Notes

def dfs(i, holding):Defines recursive helper to explore decisions at day i with holding state

if i == n:Base case: no more days means no profit

if holding:If currently holding stock, decide to sell or hold

sell = dfs(i+1, False) + prices[i]Sell stock today and add today's price to profit

hold = dfs(i+1, True)Hold stock and move to next day

return max(sell, hold)Choose the better of selling or holding

buy = dfs(i+1, True) - prices[i]Buy stock today, subtract price from profit

skip = dfs(i+1, False)Skip buying and move to next day

return max(buy, skip)Choose the better of buying or skipping

public class Solution {
    public int maxProfit(int[] prices) {
        return dfs(prices, 0, false);
    }
    private int dfs(int[] prices, int i, boolean holding) {
        if (i == prices.length) return 0;
        if (holding) {
            int sell = dfs(prices, i + 1, false) + prices[i];
            int hold = dfs(prices, i + 1, true);
            return Math.max(sell, hold);
        } else {
            int buy = dfs(prices, i + 1, true) - prices[i];
            int skip = dfs(prices, i + 1, false);
            return Math.max(buy, skip);
        }
    }
    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.maxProfit(new int[]{7,1,5,3,6,4})); // 7
    }
}

Line Notes

public int maxProfit(int[] prices)Entry point calling recursive dfs

if (i == prices.length) return 0;Base case: no more days to trade

if (holding)If holding stock, decide to sell or hold

int sell = dfs(prices, i + 1, false) + prices[i];Sell stock today and add price

int hold = dfs(prices, i + 1, true);Hold stock and continue

return Math.max(sell, hold);Choose max profit between selling and holding

int buy = dfs(prices, i + 1, true) - prices[i];Buy stock today, subtract price

int skip = dfs(prices, i + 1, false);Skip buying

return Math.max(buy, skip);Choose max profit between buying and skipping

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        return dfs(prices, 0, false);
    }
private:
    int dfs(vector<int>& prices, int i, bool holding) {
        if (i == prices.size()) return 0;
        if (holding) {
            int sell = dfs(prices, i + 1, false) + prices[i];
            int hold = dfs(prices, i + 1, true);
            return max(sell, hold);
        } else {
            int buy = dfs(prices, i + 1, true) - prices[i];
            int skip = dfs(prices, i + 1, false);
            return max(buy, skip);
        }
    }
};

int main() {
    Solution sol;
    vector<int> prices = {7,1,5,3,6,4};
    cout << sol.maxProfit(prices) << endl; // 7
    return 0;
}

Line Notes

int dfs(vector<int>& prices, int i, bool holding)Recursive helper exploring decisions at day i

if (i == prices.size()) return 0;Base case: no more days

if (holding)If holding stock, decide sell or hold

int sell = dfs(prices, i + 1, false) + prices[i];Sell stock and add price

int hold = dfs(prices, i + 1, true);Hold stock

return max(sell, hold);Choose max profit

int buy = dfs(prices, i + 1, true) - prices[i];Buy stock subtracting price

int skip = dfs(prices, i + 1, false);Skip buying

return max(buy, skip);Choose max profit

function maxProfit(prices) {
    const n = prices.length;
    function dfs(i, holding) {
        if (i === n) return 0;
        if (holding) {
            const sell = dfs(i + 1, false) + prices[i];
            const hold = dfs(i + 1, true);
            return Math.max(sell, hold);
        } else {
            const buy = dfs(i + 1, true) - prices[i];
            const skip = dfs(i + 1, false);
            return Math.max(buy, skip);
        }
    }
    return dfs(0, false);
}

// Example usage
console.log(maxProfit([7,1,5,3,6,4])); // 7

Line Notes

function dfs(i, holding)Recursive function exploring decisions

if (i === n) return 0;Base case: no more days

if (holding)If holding stock, decide sell or hold

const sell = dfs(i + 1, false) + prices[i];Sell stock and add price

const hold = dfs(i + 1, true);Hold stock

return Math.max(sell, hold);Choose max profit

const buy = dfs(i + 1, true) - prices[i];Buy stock subtracting price

const skip = dfs(i + 1, false);Skip buying

return Math.max(buy, skip);Choose max profit

⏱

Complexity

TimeO(2^n)

SpaceO(n) recursion stack

Each day has two states (holding or not), and each state branches into two decisions, leading to exponential calls.

💡 For n=20, this means over a million calls, which is impractical.

Interview Verdict: TLE

This approach is too slow for large inputs but is essential to understand the problem's structure.

🧠

Top-Down Memoization

💡 Memoization caches results of recursive calls to avoid recomputation, drastically improving efficiency while keeping the recursive intuition.

Intuition

Store results of dfs(i, holding) in a cache so repeated calls return instantly.

Algorithm

1. Create a memo dictionary keyed by (day, holding).
2. Before recursive call, check if result is cached.
3. If cached, return it immediately.
4. Otherwise, compute recursively and store in cache.
5. Return cached result.

💡 Memoization turns exponential recursion into polynomial time by reusing results.

Recurrence:Same as brute force: f(i, holding) = max(...)

</>

Code

def maxProfit(prices):
    n = len(prices)
    memo = {}
    def dfs(i, holding):
        if i == n:
            return 0
        if (i, holding) in memo:
            return memo[(i, holding)]
        if holding:
            sell = dfs(i+1, False) + prices[i]
            hold = dfs(i+1, True)
            memo[(i, holding)] = max(sell, hold)
        else:
            buy = dfs(i+1, True) - prices[i]
            skip = dfs(i+1, False)
            memo[(i, holding)] = max(buy, skip)
        return memo[(i, holding)]
    return dfs(0, False)

if __name__ == '__main__':
    print(maxProfit([7,1,5,3,6,4]))  # 7

Line Notes

memo = {}Initialize cache to store computed results

if (i, holding) in memo:Check if result already computed to avoid recomputation

memo[(i, holding)] = max(sell, hold)Store computed max profit for holding state

memo[(i, holding)] = max(buy, skip)Store computed max profit for not holding state

return memo[(i, holding)]Return cached or newly computed result

import java.util.*;
public class Solution {
    private Map<String, Integer> memo = new HashMap<>();
    public int maxProfit(int[] prices) {
        return dfs(prices, 0, false);
    }
    private int dfs(int[] prices, int i, boolean holding) {
        if (i == prices.length) return 0;
        String key = i + "," + holding;
        if (memo.containsKey(key)) return memo.get(key);
        int result;
        if (holding) {
            int sell = dfs(prices, i + 1, false) + prices[i];
            int hold = dfs(prices, i + 1, true);
            result = Math.max(sell, hold);
        } else {
            int buy = dfs(prices, i + 1, true) - prices[i];
            int skip = dfs(prices, i + 1, false);
            result = Math.max(buy, skip);
        }
        memo.put(key, result);
        return result;
    }
    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.maxProfit(new int[]{7,1,5,3,6,4})); // 7
    }
}

Line Notes

private Map<String, Integer> memo = new HashMap<>();Cache results keyed by day and holding state

String key = i + "," + holding;Create unique key for memoization

if (memo.containsKey(key)) return memo.get(key);Return cached result if available

memo.put(key, result);Store computed result in cache

return result;Return computed or cached result

#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;

class Solution {
    unordered_map<string, int> memo;
public:
    int maxProfit(vector<int>& prices) {
        return dfs(prices, 0, false);
    }
private:
    int dfs(vector<int>& prices, int i, bool holding) {
        if (i == prices.size()) return 0;
        string key = to_string(i) + "," + (holding ? "1" : "0");
        if (memo.count(key)) return memo[key];
        int result;
        if (holding) {
            int sell = dfs(prices, i + 1, false) + prices[i];
            int hold = dfs(prices, i + 1, true);
            result = max(sell, hold);
        } else {
            int buy = dfs(prices, i + 1, true) - prices[i];
            int skip = dfs(prices, i + 1, false);
            result = max(buy, skip);
        }
        memo[key] = result;
        return result;
    }
};

int main() {
    Solution sol;
    vector<int> prices = {7,1,5,3,6,4};
    cout << sol.maxProfit(prices) << endl; // 7
    return 0;
}

Line Notes

unordered_map<string, int> memo;Cache results with string keys

string key = to_string(i) + "," + (holding ? "1" : "0");Create unique key for memo

if (memo.count(key)) return memo[key];Return cached result if exists

memo[key] = result;Store computed result

return result;Return result

function maxProfit(prices) {
    const n = prices.length;
    const memo = new Map();
    function dfs(i, holding) {
        if (i === n) return 0;
        const key = i + ',' + holding;
        if (memo.has(key)) return memo.get(key);
        let result;
        if (holding) {
            const sell = dfs(i + 1, false) + prices[i];
            const hold = dfs(i + 1, true);
            result = Math.max(sell, hold);
        } else {
            const buy = dfs(i + 1, true) - prices[i];
            const skip = dfs(i + 1, false);
            result = Math.max(buy, skip);
        }
        memo.set(key, result);
        return result;
    }
    return dfs(0, false);
}

console.log(maxProfit([7,1,5,3,6,4])); // 7

Line Notes

const memo = new Map();Initialize cache for memoization

const key = i + ',' + holding;Create unique key for caching

if (memo.has(key)) return memo.get(key);Return cached result if present

memo.set(key, result);Store computed result

return result;Return result

⏱

Complexity

TimeO(n)

SpaceO(n)

Memoization ensures each state (day, holding) is computed once, total 2*n states.

💡 For n=10^5, this reduces calls from exponential to linear, making it efficient.

Interview Verdict: Accepted

Memoization makes the recursive approach practical for large inputs.

🧠

Bottom-Up Tabulation (State Machine DP)

💡 Tabulation builds the solution iteratively from the base case, which is often easier to debug and understand than recursion.

Intuition

Use two arrays to track max profit each day when holding or not holding stock, updating day by day.

Algorithm

1. Initialize dp arrays for holding and not holding states on day 0.
2. Iterate from day 1 to n-1, updating dp based on previous day states and today's price.
3. For not holding, max of (not holding yesterday, or selling today).
4. For holding, max of (holding yesterday, or buying today).
5. Return dp[n-1][0] as max profit with no stock held at the end.

💡 This approach explicitly tracks states and transitions, making the logic transparent.

Recurrence:dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i]) dp[i][1] = max(dp[i-1][1], dp[i-1][0] - prices[i])

</>

Code

def maxProfit(prices):
    n = len(prices)
    dp = [[0]*2 for _ in range(n)]
    dp[0][0] = 0
    dp[0][1] = -prices[0]
    for i in range(1, n):
        dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i])
        dp[i][1] = max(dp[i-1][1], dp[i-1][0] - prices[i])
    return dp[-1][0]

if __name__ == '__main__':
    print(maxProfit([7,1,5,3,6,4]))  # 7

Line Notes

dp = [[0]*2 for _ in range(n)]Create dp table with two states per day

dp[0][0] = 0No stock held on day 0 means zero profit

dp[0][1] = -prices[0]Holding stock on day 0 means buying at prices[0]

dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i])Max profit not holding stock today: rest or sell

dp[i][1] = max(dp[i-1][1], dp[i-1][0] - prices[i])Max profit holding stock today: rest or buy

public class Solution {
    public int maxProfit(int[] prices) {
        int n = prices.length;
        int[][] dp = new int[n][2];
        dp[0][0] = 0;
        dp[0][1] = -prices[0];
        for (int i = 1; i < n; i++) {
            dp[i][0] = Math.max(dp[i-1][0], dp[i-1][1] + prices[i]);
            dp[i][1] = Math.max(dp[i-1][1], dp[i-1][0] - prices[i]);
        }
        return dp[n-1][0];
    }
    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.maxProfit(new int[]{7,1,5,3,6,4})); // 7
    }
}

Line Notes

int[][] dp = new int[n][2];Create dp table for two states per day

dp[0][0] = 0;No stock held on day 0 profit zero

dp[0][1] = -prices[0];Holding stock on day 0 means buying

dp[i][0] = Math.max(dp[i-1][0], dp[i-1][1] + prices[i]);Max profit not holding stock today

dp[i][1] = Math.max(dp[i-1][1], dp[i-1][0] - prices[i]);Max profit holding stock today

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int n = prices.size();
        vector<vector<int>> dp(n, vector<int>(2, 0));
        dp[0][0] = 0;
        dp[0][1] = -prices[0];
        for (int i = 1; i < n; i++) {
            dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i]);
            dp[i][1] = max(dp[i-1][1], dp[i-1][0] - prices[i]);
        }
        return dp[n-1][0];
    }
};

int main() {
    Solution sol;
    vector<int> prices = {7,1,5,3,6,4};
    cout << sol.maxProfit(prices) << endl; // 7
    return 0;
}

Line Notes

vector<vector<int>> dp(n, vector<int>(2, 0));Initialize dp table with two states

dp[0][0] = 0;No stock held on day 0 profit zero

dp[0][1] = -prices[0];Holding stock on day 0 means buying

dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i]);Max profit not holding stock today

dp[i][1] = max(dp[i-1][1], dp[i-1][0] - prices[i]);Max profit holding stock today

function maxProfit(prices) {
    const n = prices.length;
    const dp = Array.from({length: n}, () => [0, 0]);
    dp[0][0] = 0;
    dp[0][1] = -prices[0];
    for (let i = 1; i < n; i++) {
        dp[i][0] = Math.max(dp[i-1][0], dp[i-1][1] + prices[i]);
        dp[i][1] = Math.max(dp[i-1][1], dp[i-1][0] - prices[i]);
    }
    return dp[n-1][0];
}

console.log(maxProfit([7,1,5,3,6,4])); // 7

Line Notes

const dp = Array.from({length: n}, () => [0, 0]);Create dp table with two states per day

dp[0][0] = 0;No stock held on day 0 profit zero

dp[0][1] = -prices[0];Holding stock on day 0 means buying

dp[i][0] = Math.max(dp[i-1][0], dp[i-1][1] + prices[i]);Max profit not holding stock today

dp[i][1] = Math.max(dp[i-1][1], dp[i-1][0] - prices[i]);Max profit holding stock today

⏱

Complexity

TimeO(n)

SpaceO(n)

We fill dp table once for n days with constant states.

💡 For n=10^5, this is efficient and practical.

Interview Verdict: Accepted

This is the standard DP solution for this problem.

🧠

Space Optimized DP

💡 Since dp[i] depends only on dp[i-1], we can optimize space by storing only previous day states.

Intuition

Keep track of only two variables for holding and not holding states, updating them as we iterate.

Algorithm

1. Initialize two variables for day 0 holding and not holding states.
2. Iterate through prices updating these variables based on previous values.
3. For not holding, max of previous not holding or selling today.
4. For holding, max of previous holding or buying today.
5. Return the not holding state after last day.

💡 This reduces space from O(n) to O(1) without changing logic.

Recurrence:same as tabulation

</>

Code

def maxProfit(prices):
    n = len(prices)
    not_holding = 0
    holding = -prices[0]
    for i in range(1, n):
        prev_not_holding = not_holding
        not_holding = max(not_holding, holding + prices[i])
        holding = max(holding, prev_not_holding - prices[i])
    return not_holding

if __name__ == '__main__':
    print(maxProfit([7,1,5,3,6,4]))  # 7

Line Notes

not_holding = 0Initial profit when not holding stock is zero

holding = -prices[0]Initial profit when holding stock is negative price of first day

prev_not_holding = not_holdingStore previous not holding before updating

not_holding = max(not_holding, holding + prices[i])Max profit not holding stock today: rest or sell

holding = max(holding, prev_not_holding - prices[i])Max profit holding stock today: rest or buy

public class Solution {
    public int maxProfit(int[] prices) {
        int notHolding = 0;
        int holding = -prices[0];
        for (int i = 1; i < prices.length; i++) {
            int prevNotHolding = notHolding;
            notHolding = Math.max(notHolding, holding + prices[i]);
            holding = Math.max(holding, prevNotHolding - prices[i]);
        }
        return notHolding;
    }
    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.maxProfit(new int[]{7,1,5,3,6,4})); // 7
    }
}

Line Notes

int notHolding = 0;Initial profit when not holding stock

int holding = -prices[0];Initial profit when holding stock

int prevNotHolding = notHolding;Store previous not holding before updating

notHolding = Math.max(notHolding, holding + prices[i]);Update not holding profit

holding = Math.max(holding, prevNotHolding - prices[i]);Update holding profit

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int notHolding = 0;
        int holding = -prices[0];
        for (int i = 1; i < prices.size(); i++) {
            int prevNotHolding = notHolding;
            notHolding = max(notHolding, holding + prices[i]);
            holding = max(holding, prevNotHolding - prices[i]);
        }
        return notHolding;
    }
};

int main() {
    Solution sol;
    vector<int> prices = {7,1,5,3,6,4};
    cout << sol.maxProfit(prices) << endl; // 7
    return 0;
}

Line Notes

int notHolding = 0;Initial profit not holding stock

int holding = -prices[0];Initial profit holding stock

int prevNotHolding = notHolding;Store previous not holding before updating

notHolding = max(notHolding, holding + prices[i]);Update not holding profit

holding = max(holding, prevNotHolding - prices[i]);Update holding profit

function maxProfit(prices) {
    let notHolding = 0;
    let holding = -prices[0];
    for (let i = 1; i < prices.length; i++) {
        let prevNotHolding = notHolding;
        notHolding = Math.max(notHolding, holding + prices[i]);
        holding = Math.max(holding, prevNotHolding - prices[i]);
    }
    return notHolding;
}

console.log(maxProfit([7,1,5,3,6,4])); // 7

Line Notes

let notHolding = 0;Initial profit not holding stock

let holding = -prices[0];Initial profit holding stock

let prevNotHolding = notHolding;Store previous not holding before updating

notHolding = Math.max(notHolding, holding + prices[i]);Update not holding profit

holding = Math.max(holding, prevNotHolding - prices[i]);Update holding profit

⏱

Complexity

TimeO(n)

SpaceO(1)

Only constant space used to track states, linear time to iterate prices.

💡 This is the most efficient solution in both time and space.

Interview Verdict: Accepted

This is the best approach to implement in interviews for this problem.

📊

All Approaches - One-Glance Tradeoffs

💡 In interviews, implement the bottom-up tabulation or space optimized DP for best balance of clarity and efficiency.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force	O(2^n)	O(n) recursion stack	Yes (deep recursion)	Yes	Mention only - never code
2. Top-Down Memoization	O(n)	O(n)	No (due to memoization)	Yes	Good to explain optimization over brute force
3. Bottom-Up Tabulation	O(n)	O(n)	No	Yes	Best for clarity and accepted solution
4. Space Optimized DP	O(n)	O(1)	No	No (without extra tracking)	Mention after tabulation to show mastery

💼

Interview Strategy

💡 Use this guide to understand the problem deeply, practice all approaches, and know when to optimize. Read it before every mock interview to build confidence.

How to Present

Step 1: Clarify problem constraints and ask about transaction limits.Step 2: Present brute force recursion to show understanding of problem structure.Step 3: Optimize with memoization to improve efficiency.Step 4: Explain bottom-up DP tabulation for clarity and iterative solution.Step 5: Mention space optimization to demonstrate mastery.

Time Allocation

Clarify: 2min → Approach: 5min → Code: 10min → Test: 3min. Total ~20min

What the Interviewer Tests

Interviewer tests your understanding of DP states, ability to optimize recursion, and code correctness under large inputs.

Common Follow-ups

• What if there is a cooldown period after selling? → Modify states to include cooldown.
• What if there is a transaction fee? → Adjust profit calculation when selling.
• What if only k transactions allowed? → Use 3D DP with transaction count.
• Can you do it in O(n) time and O(1) space? → Yes, with space optimized DP.

💡 These follow-ups test your ability to adapt the DP model to variations.

🔍

Pattern Recognition

When to Use

1) Problem involves stock prices or sequences with buy/sell decisions; 2) Unlimited or limited transactions allowed; 3) Need to maximize profit; 4) Constraints suggest DP over greedy.

Signature Phrases

buy and sell stock multiple timesmaximize profit with unlimited transactions

NOT This Pattern When

Problems with only one transaction or no transaction limits but different constraints (e.g., no holding multiple stocks) are different patterns.

Similar Problems

Best Time to Buy and Sell Stock I - simpler with one transactionBest Time to Buy and Sell Stock with Cooldown - adds cooldown stateBest Time to Buy and Sell Stock with Transaction Fee - adds fee to transitions

Practice

1. You are given a list of daily stock prices and a maximum number of allowed transactions. You want to maximize profit by buying and selling stocks, but you cannot hold more than one stock at a time and must complete each transaction before starting another. Which algorithmic approach guarantees an optimal solution for this problem?

easy

A. Divide and conquer splitting the price array and merging results

B. Greedy algorithm that buys whenever price is lower than the next day and sells the next day

C. Pure brute force recursion exploring all buy/sell combinations without memoization

D. Dynamic programming using state machines to track buy/sell states for each transaction count

Solution

1. Step 1: Understand problem constraints and limitations of greedy

   The problem limits the number of transactions and requires maximizing profit with buy/sell states, which greedy fails to handle optimally.

2. Step 2: Identify suitable algorithm

   Dynamic programming with state machines tracks holding and not holding states per transaction count, ensuring all possibilities are considered efficiently.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Greedy fails on multiple transactions; DP state machines handle all cases [OK]

Hint: DP with states handles transaction limits optimally [OK]

Common Mistakes:

• Assuming greedy always works for stock problems

2. Consider the following Python code for maximizing stock profit with transaction fee:

def maxProfit(prices, fee):
    cash, hold = 0, -prices[0]
    for price in prices[1:]:
        cash = max(cash, hold + price - fee)
        hold = max(hold, cash - price)
    return cash

prices = [1, 3, 2]
fee = 1
print(maxProfit(prices, fee))

What is the output of this code?

easy

A. 1

B. 0

C. 3

D. 2

Solution

1. Step 1: Initialize variables

   cash = 0, hold = -1 (buy at price 1)

2. Step 2: Iterate over prices

   Price=3: cash = max(0, -1 + 3 - 1) = max(0,1) = 1; hold = max(-1, 1 - 3) = max(-1,-2) = -1 Price=2: cash = max(1, -1 + 2 - 1) = max(1,0) = 1; hold = max(-1, 1 - 2) = max(-1,-1) = -1

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Final cash is 1, representing max profit after fee [OK]

Hint: Track cash and hold updates carefully [OK]

Common Mistakes:

• Off-by-one in loop
• Forgetting fee subtraction

3. Consider the following Python code implementing the optimal solution for the House Robber II problem. What is the final output when the input is [2, 3, 2]?

def rob_linear(nums, start, end):
    prev, curr = 0, 0
    for i in range(start, end + 1):
        prev, curr = curr, max(curr, prev + nums[i])
    return curr

def rob(nums):
    n = len(nums)
    if n == 1:
        return nums[0]
    return max(rob_linear(nums, 0, n - 2), rob_linear(nums, 1, n - 1))

print(rob([2,3,2]))

easy

A. 4

B. 2

C. 3

D. 5

Solution

1. Step 1: Trace rob_linear(nums, 0, 1)

   nums[0]=2, nums[1]=3 Iteration i=0: prev=0, curr=0 -> prev=0, curr=max(0,0+2)=2 Iteration i=1: prev=2, curr=max(2,0+3)=3 Return 3

2. Step 2: Trace rob_linear(nums, 1, 2)

   nums[1]=3, nums[2]=2 Iteration i=1: prev=0, curr=0 -> prev=0, curr=max(0,0+3)=3 Iteration i=2: prev=3, curr=max(3,0+2)=3 Return 3 Max(3,3) = 3

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Both cases yield 3, final output is 3 [OK]

Hint: Trace both linear cases and pick max [OK]

Common Mistakes:

• Off-by-one in loop range
• Confusing which subarray to use
• Incorrect max calculation

4. You are given a string s and a dictionary of words. You need to determine if s can be segmented into a space-separated sequence of one or more dictionary words. Which algorithmic approach guarantees an optimal solution for this problem?

easy

A. Pure brute force recursion checking all possible segmentations without memoization

B. Greedy approach that tries to match the longest prefix word repeatedly

C. Dynamic Programming that builds up a boolean array indicating segmentability up to each index

D. Sorting the dictionary and using binary search to find words in the string

Solution

1. Step 1: Understand the problem constraints

   The problem requires checking if the string can be segmented into dictionary words, which involves overlapping subproblems and optimal substructure.

2. Step 2: Identify the suitable algorithmic pattern

   Dynamic Programming (DP) is appropriate because it stores results of subproblems (segmentability up to index i) to avoid recomputation, guaranteeing an optimal solution.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   DP uses boolean array to track valid breaks [OK]

Hint: DP with boolean array tracks segmentability [OK]

Common Mistakes:

• Thinking greedy longest prefix always works
• Assuming brute force is efficient enough
• Using binary search without DP

5. What is the time complexity of the optimal bottom-up dynamic programming solution for the minimum cost climbing stairs problem, and why?

medium

A. O(n) because each step computes cost using only two previous states

B. O(n²) because each step depends on all previous steps

C. O(2^n) due to exponential recursion calls

D. O(n log n) because of sorting costs before processing

Solution

1. Step 1: Analyze loop structure

   The bottom-up DP iterates once through the cost array of length n.

2. Step 2: Check dependencies per iteration

   Each iteration computes current cost using only two previous values, constant time per iteration.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Single pass with O(1) work per step -> O(n) total [OK]

Hint: DP uses constant work per step, linear total time [OK]

Common Mistakes:

• Assuming quadratic due to nested loops
• Confusing recursion with DP iteration
• Thinking sorting is involved