Best Time to Buy and Sell Stock (1 tx)

🎯

Best Time to Buy and Sell Stock (1 tx)

easyDPAmazonFacebookGoogle

Imagine you are an investor who wants to maximize profit by buying and selling a single stock once over a period of days. You want to know the best day to buy and the best day to sell to maximize your gain.

💡 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 a naive greedy approach can fail. Understanding the brute force approach helps build intuition for the optimal DP solution.

📋

Problem Statement

Given an array prices where prices[i] is the price of a given stock on the ith day, find the maximum profit you can achieve by making at most one transaction (i.e., buy one and sell one share of the stock). If no profit can be made, return 0.

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

💡

Example

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

Output5

Buy on day 2 (price=1) and sell on day 5 (price=6), profit = 6-1 = 5.

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

Output0

No transaction is done, so max profit = 0.

• Only one day → output 0 (cannot sell)
• Prices are all the same → output 0 (no profit)
• Prices strictly decreasing → output 0 (no profit)
• Prices strictly increasing → output max difference between last and first day

🔁

Why DP?

Why greedy fails:

A greedy approach that picks the maximum difference by scanning once can fail if it tries to sell before buying. For example, prices = [3,2,6,1,4], a naive greedy might pick 6-2=4 but misses that buying at 1 and selling at 4 yields 3, which is less but valid. The problem requires tracking minimum price so far, which is a DP insight.

DP state:

dp[i] represents the maximum profit achievable from day 0 up to day i by making at most one transaction.

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

At day i, either keep the previous max profit or sell today at price[i] after buying at the lowest price seen so far.

⚠️

Common Mistakes

Trying to sell before buying

Incorrect profit calculation or negative profits

✅ Always track minimum price seen so far before calculating profit

Using nested loops in large inputs

Time limit exceeded (TLE) in interviews

✅ Use one-pass approach with tracking min price and max profit

Not handling edge cases like single day or decreasing prices

Wrong output or runtime errors

✅ Return 0 if no profit is possible and handle small input sizes

Updating max profit before updating min price

Incorrect profit calculation on the same day

✅ Update min price first, then calculate profit

Using extra space unnecessarily

Higher memory usage and complexity

✅ Use space optimized approach with variables instead of arrays

🧠

Brute Force (Nested Loops)

💡 This approach is the most straightforward and helps understand the problem by checking every possible buy and sell day combination. It is inefficient but builds intuition.

Intuition

Try every pair of days (buy day and sell day) and calculate the profit. Keep track of the maximum profit found.

Algorithm

1. Initialize max_profit to 0.
2. For each day i, consider it as the buy day.
3. For each day j > i, consider it as the sell day and calculate profit = prices[j] - prices[i].
4. Update max_profit if profit is greater than current max_profit.
5. Return max_profit after checking all pairs.

💡 The nested loops make it hard to see efficiency, but it clearly checks all possibilities.

Recurrence:Not applicable for brute force.

</>

Code

def maxProfit(prices):
    max_profit = 0
    n = len(prices)
    for i in range(n):
        for j in range(i+1, n):
            profit = prices[j] - prices[i]
            if profit > max_profit:
                max_profit = profit
    return max_profit

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

Line Notes

max_profit = 0Initialize max profit to zero since no transactions done yet

for i in range(n)Outer loop selects the buy day

for j in range(i+1, n)Inner loop selects the sell day after buy day

profit = prices[j] - prices[i]Calculate profit for this buy-sell pair

if profit > max_profitUpdate max profit if current profit is better

public class Solution {
    public static int maxProfit(int[] prices) {
        int maxProfit = 0;
        int n = prices.length;
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                int profit = prices[j] - prices[i];
                if (profit > maxProfit) {
                    maxProfit = profit;
                }
            }
        }
        return maxProfit;
    }

    public static void main(String[] args) {
        int[] prices = {7,1,5,3,6,4};
        System.out.println(maxProfit(prices)); // Output: 5
    }
}

Line Notes

int maxProfit = 0;Initialize max profit to zero before any transactions

for (int i = 0; i < n; i++)Outer loop picks buy day

for (int j = i + 1; j < n; j++)Inner loop picks sell day after buy day

int profit = prices[j] - prices[i];Calculate profit for current buy-sell pair

if (profit > maxProfit)Update max profit if current profit is higher

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

int maxProfit(vector<int>& prices) {
    int maxProfit = 0;
    int n = prices.size();
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            int profit = prices[j] - prices[i];
            if (profit > maxProfit) {
                maxProfit = profit;
            }
        }
    }
    return maxProfit;
}

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

Line Notes

int maxProfit = 0;Initialize max profit to zero before checking pairs

for (int i = 0; i < n; i++)Outer loop selects buy day

for (int j = i + 1; j < n; j++)Inner loop selects sell day after buy day

int profit = prices[j] - prices[i];Calculate profit for current pair

if (profit > maxProfit)Update max profit if current profit is better

function maxProfit(prices) {
    let maxProfit = 0;
    const n = prices.length;
    for (let i = 0; i < n; i++) {
        for (let j = i + 1; j < n; j++) {
            let profit = prices[j] - prices[i];
            if (profit > maxProfit) {
                maxProfit = profit;
            }
        }
    }
    return maxProfit;
}

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

Line Notes

let maxProfit = 0;Initialize max profit to zero before any transactions

for (let i = 0; i < n; i++)Outer loop picks buy day

for (let j = i + 1; j < n; j++)Inner loop picks sell day after buy day

let profit = prices[j] - prices[i];Calculate profit for current buy-sell pair

if (profit > maxProfit)Update max profit if current profit is higher

⏱

Complexity

TimeO(n^2)

SpaceO(1)

Two nested loops each up to n, so n*n = n^2 operations.

💡 For n=1000, this means about 1,000,000 operations, which is slow for large inputs.

Interview Verdict: TLE for large inputs; useful only to introduce the problem.

This approach is too slow for large inputs but helps understand the problem.

🧠

One Pass with Tracking Minimum Price

💡 This approach improves efficiency by scanning the prices once, tracking the minimum price so far and calculating max profit on the fly.

Intuition

Keep track of the lowest price seen so far and calculate potential profit at each day by selling at current price. Update max profit accordingly.

Algorithm

1. Initialize min_price to a very large number and max_profit to 0.
2. Iterate through each price in the array.
3. Update min_price if current price is lower than min_price.
4. Calculate profit by subtracting min_price from current price.
5. Update max_profit if this profit is greater than current max_profit.
6. Return max_profit after processing all prices.

💡 This approach is easier to implement and understand once you grasp the idea of tracking minimum price.

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

</>

Code

def maxProfit(prices):
    min_price = float('inf')
    max_profit = 0
    for price in prices:
        if price < min_price:
            min_price = price
        elif price - min_price > max_profit:
            max_profit = price - min_price
    return max_profit

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

Line Notes

min_price = float('inf')Initialize min_price to infinity to ensure first price updates it

max_profit = 0Initialize max profit to zero

for price in prices:Iterate over each day's price

if price < min_price:Update min_price if current price is lower

elif price - min_price > max_profit:Update max_profit if selling today yields better profit

public class Solution {
    public static int maxProfit(int[] prices) {
        int minPrice = Integer.MAX_VALUE;
        int maxProfit = 0;
        for (int price : prices) {
            if (price < minPrice) {
                minPrice = price;
            } else if (price - minPrice > maxProfit) {
                maxProfit = price - minPrice;
            }
        }
        return maxProfit;
    }

    public static void main(String[] args) {
        int[] prices = {7,1,5,3,6,4};
        System.out.println(maxProfit(prices)); // Output: 5
    }
}

Line Notes

int minPrice = Integer.MAX_VALUE;Initialize minPrice to max int to ensure first price updates it

int maxProfit = 0;Initialize maxProfit to zero

for (int price : prices)Iterate over each price in prices

if (price < minPrice)Update minPrice if current price is lower

else if (price - minPrice > maxProfit)Update maxProfit if selling today yields better profit

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

int maxProfit(vector<int>& prices) {
    int minPrice = INT_MAX;
    int maxProfit = 0;
    for (int price : prices) {
        if (price < minPrice) {
            minPrice = price;
        } else if (price - minPrice > maxProfit) {
            maxProfit = price - minPrice;
        }
    }
    return maxProfit;
}

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

Line Notes

int minPrice = INT_MAX;Initialize minPrice to max int to ensure first price updates it

int maxProfit = 0;Initialize maxProfit to zero

for (int price : prices)Iterate over each price in prices

if (price < minPrice)Update minPrice if current price is lower

else if (price - minPrice > maxProfit)Update maxProfit if selling today yields better profit

function maxProfit(prices) {
    let minPrice = Infinity;
    let maxProfit = 0;
    for (let price of prices) {
        if (price < minPrice) {
            minPrice = price;
        } else if (price - minPrice > maxProfit) {
            maxProfit = price - minPrice;
        }
    }
    return maxProfit;
}

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

Line Notes

let minPrice = Infinity;Initialize minPrice to infinity to ensure first price updates it

let maxProfit = 0;Initialize maxProfit to zero

for (let price of prices)Iterate over each price in prices

if (price < minPrice)Update minPrice if current price is lower

else if (price - minPrice > maxProfit)Update maxProfit if selling today yields better profit

⏱

Complexity

TimeO(n)

SpaceO(1)

Single pass through prices array, constant extra space.

💡 For n=100000, this means 100000 operations, which is efficient for interviews.

Interview Verdict: Accepted and optimal for this problem.

This is the standard solution expected in interviews.

🧠

Dynamic Programming with State Array

💡 This approach explicitly uses a DP array to store max profit up to each day, making the state and recurrence clear for beginners.

Intuition

At each day, the max profit is either the same as previous day or selling today after buying at the lowest price so far.

Algorithm

1. Initialize dp array of length n with zeros.
2. Initialize min_price to prices[0].
3. Iterate from day 1 to n-1:
4. Update min_price if current price is lower.
5. Calculate profit by selling today: prices[i] - min_price.
6. Set dp[i] as max of dp[i-1] and profit.
7. Return dp[n-1] as the answer.

💡 This approach makes the recurrence explicit and easy to trace.

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

</>

Code

def maxProfit(prices):
    n = len(prices)
    dp = [0] * n
    min_price = prices[0]
    for i in range(1, n):
        if prices[i] < min_price:
            min_price = prices[i]
        dp[i] = max(dp[i-1], prices[i] - min_price)
    return dp[-1]

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

Line Notes

dp = [0] * nInitialize dp array to store max profit up to each day

min_price = prices[0]Start min_price as first day's price

for i in range(1, n)Iterate from second day to last day

if prices[i] < min_priceUpdate min_price if current price is lower

dp[i] = max(dp[i-1], prices[i] - min_price)Store max profit up to day i

public class Solution {
    public static int maxProfit(int[] prices) {
        int n = prices.length;
        int[] dp = new int[n];
        int minPrice = prices[0];
        for (int i = 1; i < n; i++) {
            if (prices[i] < minPrice) {
                minPrice = prices[i];
            }
            dp[i] = Math.max(dp[i-1], prices[i] - minPrice);
        }
        return dp[n-1];
    }

    public static void main(String[] args) {
        int[] prices = {7,1,5,3,6,4};
        System.out.println(maxProfit(prices)); // Output: 5
    }
}

Line Notes

int[] dp = new int[n];Create dp array to store max profit up to each day

int minPrice = prices[0];Initialize minPrice to first day's price

for (int i = 1; i < n; i++)Iterate from second day to last day

if (prices[i] < minPrice)Update minPrice if current price is lower

dp[i] = Math.max(dp[i-1], prices[i] - minPrice);Store max profit up to day i

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

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

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

Line Notes

vector<int> dp(n, 0);Initialize dp vector with zeros for max profit

int minPrice = prices[0];Set minPrice to first day's price

for (int i = 1; i < n; i++)Iterate from second day to last day

if (prices[i] < minPrice)Update minPrice if current price is lower

dp[i] = max(dp[i-1], prices[i] - minPrice);Store max profit up to day i

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

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

Line Notes

const dp = new Array(n).fill(0);Initialize dp array with zeros for max profit

let minPrice = prices[0];Initialize minPrice to first day's price

for (let i = 1; i < n; i++)Iterate from second day to last day

if (prices[i] < minPrice)Update minPrice if current price is lower

dp[i] = Math.max(dp[i-1], prices[i] - minPrice);Store max profit up to day i

⏱

Complexity

TimeO(n)

SpaceO(n)

Single pass with dp array of size n.

💡 Uses more memory than approach 2 but makes DP states explicit.

Interview Verdict: Accepted; useful for understanding DP formulation.

Good for teaching DP but less optimal in space.

🧠

Space Optimized DP (Tracking Variables Only)

💡 This approach optimizes space by removing the dp array and only tracking necessary variables, achieving O(1) space.

Intuition

Since dp[i] depends only on dp[i-1], we can keep track of max profit and min price with variables instead of arrays.

Algorithm

1. Initialize min_price to prices[0] and max_profit to 0.
2. Iterate through prices from day 1 to end.
3. Update min_price if current price is lower.
4. Calculate profit by selling today and update max_profit if better.
5. Return max_profit after iteration.

💡 This approach is the most efficient and uses minimal memory.

Recurrence:max_profit = max(max_profit, prices[i] - min_price); min_price = min(min_price, prices[i])

</>

Code

def maxProfit(prices):
    min_price = prices[0]
    max_profit = 0
    for i in range(1, len(prices)):
        if prices[i] < min_price:
            min_price = prices[i]
        else:
            max_profit = max(max_profit, prices[i] - min_price)
    return max_profit

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

Line Notes

min_price = prices[0]Initialize min_price to first price

max_profit = 0Initialize max_profit to zero

for i in range(1, len(prices))Iterate from second day to last day

if prices[i] < min_priceUpdate min_price if current price is lower

max_profit = max(max_profit, prices[i] - min_price)Update max_profit if selling today yields better profit

public class Solution {
    public static int maxProfit(int[] prices) {
        int minPrice = prices[0];
        int maxProfit = 0;
        for (int i = 1; i < prices.length; i++) {
            if (prices[i] < minPrice) {
                minPrice = prices[i];
            } else {
                maxProfit = Math.max(maxProfit, prices[i] - minPrice);
            }
        }
        return maxProfit;
    }

    public static void main(String[] args) {
        int[] prices = {7,1,5,3,6,4};
        System.out.println(maxProfit(prices)); // Output: 5
    }
}

Line Notes

int minPrice = prices[0];Initialize minPrice to first price

int maxProfit = 0;Initialize maxProfit to zero

for (int i = 1; i < prices.length; i++)Iterate from second day to last day

if (prices[i] < minPrice)Update minPrice if current price is lower

maxProfit = Math.max(maxProfit, prices[i] - minPrice);Update maxProfit if selling today yields better profit

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

int maxProfit(vector<int>& prices) {
    int minPrice = prices[0];
    int maxProfit = 0;
    for (int i = 1; i < prices.size(); i++) {
        if (prices[i] < minPrice) {
            minPrice = prices[i];
        } else {
            maxProfit = max(maxProfit, prices[i] - minPrice);
        }
    }
    return maxProfit;
}

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

Line Notes

int minPrice = prices[0];Initialize minPrice to first price

int maxProfit = 0;Initialize maxProfit to zero

for (int i = 1; i < prices.size(); i++)Iterate from second day to last day

if (prices[i] < minPrice)Update minPrice if current price is lower

maxProfit = max(maxProfit, prices[i] - minPrice);Update maxProfit if selling today yields better profit

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

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

Line Notes

let minPrice = prices[0];Initialize minPrice to first price

let maxProfit = 0;Initialize maxProfit to zero

for (let i = 1; i < prices.length; i++)Iterate from second day to last day

if (prices[i] < minPrice)Update minPrice if current price is lower

maxProfit = Math.max(maxProfit, prices[i] - minPrice);Update maxProfit if selling today yields better profit

⏱

Complexity

TimeO(n)

SpaceO(1)

Single pass with constant extra space.

💡 Most efficient approach in both time and space.

Interview Verdict: Accepted; best approach to code in interviews.

This is the recommended approach for interviews due to simplicity and efficiency.

📊

All Approaches - One-Glance Tradeoffs

💡 The one-pass tracking min price approach (Approach 2 or 4) is the best to code in 95% of interviews due to its clarity and efficiency.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force	O(n^2)	O(1)	No	N/A	Mention only - never code
2. One Pass Tracking Min Price	O(n)	O(1)	No	Yes, with extra tracking	Code this approach
3. DP with State Array	O(n)	O(n)	No	Yes	Good for explaining DP but less optimal
4. Space Optimized DP	O(n)	O(1)	No	Yes, with extra variables	Best approach to code

💼

Interview Strategy

💡 Use this guide to understand the problem deeply, practice all approaches, and prepare to explain tradeoffs clearly in interviews.

How to Present

Step 1: Clarify the problem and constraints with the interviewer.Step 2: Present the brute force approach to show understanding of the problem.Step 3: Explain inefficiency and propose the optimized one-pass solution.Step 4: Write clean, efficient code for the one-pass approach.Step 5: Test code with edge cases and discuss time/space complexity.

Time Allocation

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

What the Interviewer Tests

Interviewer tests your problem understanding, ability to optimize brute force, and coding skills for the optimal solution.

Common Follow-ups

• What if multiple transactions are allowed? → Use DP with multiple states.
• What if there is a cooldown period? → Modify DP states to include cooldown.
• What if there is a transaction fee? → Adjust profit calculation accordingly.
• How to reconstruct the buy and sell days? → Track indices when updating max profit.

💡 These follow-ups test your ability to extend the base problem to more complex variants.

🔍

Pattern Recognition

When to Use

1) Problem involves stock prices or sequences over time, 2) Asked to maximize profit with constraints, 3) Single or limited transactions, 4) Requires tracking min/max values or states.

Signature Phrases

'You want to maximize profit by buying and selling once''Given an array of prices, find the best day to buy and sell'

NOT This Pattern When

Problems that require counting subsequences or subsets, or that involve unlimited transactions without constraints.

Similar Problems

Best Time to Buy and Sell Stock II - multiple transactions allowedBest Time to Buy and Sell Stock with Cooldown - cooldown days after sellingBest Time to Buy and Sell Stock with Transaction Fee - fee per transaction

Practice

1. Consider the following Python code for climbing stairs:

def climb_stairs(n):
    if n <= 1:
        return 1
    first, second = 1, 1
    for _ in range(2, n + 1):
        current = first + second
        first, second = second, current
    return second

print(climb_stairs(4))

What is the value of the variable current during the last iteration of the loop?

easy

A. 4

B. 2

C. 3

D. 5

Solution

1. Step 1: Trace variable values for n=4

   Initialize first=1, second=1. Iterations: - i=2: current=1+1=2; first=1, second=2 - i=3: current=1+2=3; first=2, second=3 - i=4: current=2+3=5; first=3, second=5

2. Step 2: Identify last iteration's current value

   The last iteration is i=4, current=5.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Last current computed is 5 for n=4 [OK]

Hint: Trace loop iterations carefully to find current value [OK]

Common Mistakes:

• Confusing loop bounds and off-by-one errors
• Returning previous current instead of last

2. Consider the following code snippet implementing the optimal decoding count algorithm. What is the value of curr after the second iteration of the loop when input s = "226"?

easy

A. 3

B. 1

C. 2

D. 0

Solution

1. Step 1: Trace first iteration (i=1)

   For s[1] = '2', curr = prev1 (1) + prev2 (1) = 2, prev2=1, prev1=2 after update.

2. Step 2: Trace second iteration (i=2)

   For s[2] = '6', curr starts at 0, s[2] != '0' so curr += prev1 (2), two_digit = 26 in [10,26], curr += prev2 (1), total curr = 3.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   At second iteration curr=3 matches expected decoding count [OK]

Hint: Add prev1 if single digit valid, add prev2 if two-digit valid [OK]

Common Mistakes:

• Off-by-one in loop index or incorrect curr update

3. You are given a list of non-negative integers representing the amount of money in each house along a street. You want to maximize the total amount you can rob tonight without robbing two adjacent houses. Which algorithmic approach guarantees finding the optimal solution efficiently?

easy

A. Dynamic programming that considers robbing or skipping each house to maximize total

B. A greedy algorithm that always picks the house with the maximum amount next

C. Sorting the houses by amount and picking the top half

D. Depth-first search exploring all subsets of houses

Solution

1. Step 1: Understand problem constraints

   The problem requires maximizing sum without robbing adjacent houses, which is a classic overlapping subproblems scenario.

2. Step 2: Identify suitable algorithm

   Dynamic programming fits because it explores choices at each house (rob or skip) and uses previous results to build optimal solution.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Greedy fails on cases like [2,7,9,3,1], DP finds max 12 [OK]

Hint: DP handles overlapping subproblems and optimal substructure [OK]

Common Mistakes:

• Greedy approach fails on non-adjacent constraints

4. Given the following code for the Jump Game II problem, what is the value of the variable jumps returned when the input is [2,1,1]?

easy

A. 3

B. 2

C. 1

D. 0

Solution

1. Step 1: Trace variables for input [2,1,1]

   n=3, loop i in [0,1]. - i=0: furthest = max(0, 0+2) = 2; i == current_end (0), so jumps = 1, current_end = 2 - i=1: furthest = max(2, 1+1) = 2; i != current_end (2), no jump increment Loop ends.

2. Step 2: Return jumps

   jumps = 1 is returned, meaning minimum 1 jump to reach the end.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   One jump from index 0 to last index covers entire array [OK]

Hint: Increment jumps only when i reaches current_end [OK]

Common Mistakes:

• Incrementing jumps too early or too late
• Off-by-one errors in loop range
• Misunderstanding when to update current_end

5. Suppose the problem is modified so that you can reuse the same stock multiple times within a single transaction (i.e., buy and sell multiple times without waiting). Which modification to the DP approach correctly handles this variant?

hard

A. Modify the DP to allow buying again without decrementing transactions_left when holding a stock

B. Increase k to a very large number and use the unlimited transactions solution shortcut

C. Use the same DP but skip updating buy states to avoid multiple buys

D. Use a greedy approach to sum all positive price differences without DP

Solution

1. Step 1: Understand the reuse variant

   Reusing stock within a transaction means multiple buys/sells without reducing transaction count on buys.

2. Step 2: Modify DP state transitions

   Allow buy state updates without decrementing transactions_left, so holding state can be refreshed multiple times per transaction.

3. Step 3: Why other options fail

   Unlimited transactions shortcut ignores transaction limit; skipping buy updates breaks profit calculation; greedy fails with transaction constraints.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Correct DP modification respects transaction count and allows multiple buys per transaction [OK]

Hint: Allow buy updates without reducing transactions_left [OK]

Common Mistakes:

• Using unlimited transactions shortcut incorrectly
• Skipping buy updates breaks DP correctness