Problem Description

You are given two arrays of stock prices: present and future. The present[i] represents the current price of the i-th stock, and future[i] represents what that same stock will be worth one year from now. Both arrays have the same length and are 0-indexed.

You have a fixed budget to invest in stocks. Your goal is to maximize your profit by strategically buying stocks now and selling them in the future. The constraints are:

• Each stock can be purchased at most once
• You cannot spend more than your budget
• The profit from a stock is calculated as future[i] - present[i]

For example, if a stock costs $10 now (`present[i] = 10`) and will be worth$15 in the future (future[i] = 15), buying it would cost you $10 from your budget and give you a profit of$5.

The problem asks you to find the maximum total profit you can achieve by selecting which stocks to buy within your budget constraints. This is essentially a variant of the 0/1 knapsack problem where:

• The "weight" of each item is the current price (present[i])
• The "value" of each item is the profit (future[i] - present[i])
• The "capacity" is your budget

Return the maximum profit you can make by optimally selecting which stocks to purchase.

Intuition

When looking at this problem, we need to make decisions about which stocks to buy to maximize our profit. For each stock, we have a binary choice: either buy it or skip it. This immediately suggests a decision-making problem where we need to explore different combinations.

The key insight is recognizing this as a resource allocation problem. We have limited resources (our budget) and want to maximize our return (total profit). This pattern is classic dynamic programming territory, specifically the 0/1 knapsack problem.

Think about it this way: if we're standing at stock i with some remaining budget j, we need to decide whether buying this stock will lead to better overall profit. To make this decision optimally, we need to know: "What's the best profit I could have made with the previous stocks given different budget amounts?"

This naturally leads us to define a state f[i][j] representing the maximum profit achievable when:

• We've considered the first i stocks
• We have a budget of j to work with

For each stock at position i, we face two scenarios:

1. Skip the stock: If we don't buy it, our profit remains the same as what we could achieve with the first i-1 stocks and the same budget j. So f[i][j] = f[i-1][j].

2. Buy the stock: If we buy it, we need to:

   • Check if we can afford it (j >= present[i])
   • Check if it's profitable (future[i] > present[i])
   • Calculate the new profit: previous best with reduced budget plus this stock's profit
   • This gives us f[i][j] = f[i-1][j - present[i]] + (future[i] - present[i])

We take the maximum of these two choices. By building up our solution from smaller subproblems (fewer stocks, smaller budgets) to larger ones, we ensure we find the optimal combination of stocks to purchase within our budget constraint.

Learn more about Dynamic Programming patterns.

Solution Approach

We implement the dynamic programming solution using a 2D array to store our states. Let's walk through the implementation step by step:

1. Initialize the DP Table:

f = [[0] * (budget + 1) for _ in range(len(present) + 1)]

We create a 2D array f with dimensions (n+1) × (budget+1) where n is the number of stocks. The extra row and column handle the base case where we have 0 stocks or 0 budget, which naturally have 0 profit.

2. Iterate Through Each Stock:

for i, w in enumerate(present, 1):

We iterate through each stock, where i represents the stock index (starting from 1 for our DP table) and w represents the current price of the stock (present[i-1]).

3. Consider All Budget Amounts:

for j in range(budget + 1):

For each stock, we consider all possible budget amounts from 0 to our maximum budget.

4. Apply the DP Transition:

f[i][j] = f[i - 1][j]  # Case 1: Don't buy the stock

First, we set the default value to be the profit without buying the current stock.

if j >= w and future[i - 1] > w:
    f[i][j] = max(f[i][j], f[i - 1][j - w] + future[i - 1] - w)

Then, if we have enough budget (j >= w) and the stock is profitable (future[i-1] > w), we check if buying it would give us better profit:

• f[i - 1][j - w]: The best profit from previous stocks with reduced budget
• future[i - 1] - w: The profit from this stock (sell price - buy price)

We take the maximum between not buying and buying the stock.

5. Return the Result:

return f[-1][-1]

The answer is stored in f[n][budget], which represents the maximum profit when considering all stocks with the full budget.

Time Complexity: O(n × budget) where n is the number of stocks
Space Complexity: O(n × budget) for the DP table

Note: The space complexity could be optimized to O(budget) by using a 1D array since we only need the previous row to compute the current row, but the 2D approach is more intuitive to understand.

Example Walkthrough

Let's walk through a concrete example to see how the dynamic programming solution works.

Example:

• present = [5, 10, 3] (current stock prices)
• future = [8, 12, 7] (future stock prices)
• budget = 8

Profits for each stock:

• Stock 0: profit = 8 - 5 = 3
• Stock 1: profit = 12 - 10 = 2
• Stock 2: profit = 7 - 3 = 4

Step 1: Initialize DP table We create a 4×9 table (3 stocks + 1) × (budget 8 + 1):

    Budget: 0  1  2  3  4  5  6  7  8
Stock 0:    0  0  0  0  0  0  0  0  0
Stock 1:    0  0  0  0  0  0  0  0  0
Stock 2:    0  0  0  0  0  0  0  0  0
Stock 3:    0  0  0  0  0  0  0  0  0

Step 2: Process Stock 0 (price=5, profit=3) For each budget j from 0 to 8:

• j < 5: Can't afford it, so f[1][j] = f[0][j] = 0
• j ≥ 5: Can buy it! f[1][j] = max(0, f[0][j-5] + 3) = 3

    Budget: 0  1  2  3  4  5  6  7  8
Stock 0:    0  0  0  0  0  0  0  0  0
Stock 1:    0  0  0  0  0  3  3  3  3
Stock 2:    0  0  0  0  0  0  0  0  0
Stock 3:    0  0  0  0  0  0  0  0  0

Step 3: Process Stock 1 (price=10, profit=2) For each budget j:

• j < 10: Can't afford it, so f[2][j] = f[1][j]
• Since our max budget is 8, we can never buy stock 1!

    Budget: 0  1  2  3  4  5  6  7  8
Stock 0:    0  0  0  0  0  0  0  0  0
Stock 1:    0  0  0  0  0  3  3  3  3
Stock 2:    0  0  0  0  0  3  3  3  3
Stock 3:    0  0  0  0  0  0  0  0  0

Step 4: Process Stock 2 (price=3, profit=4) For each budget j:

• j < 3: Can't afford it, f[3][j] = f[2][j]
• j = 3: f[3][3] = max(f[2][3], f[2][0] + 4) = max(0, 0+4) = 4
• j = 4: f[3][4] = max(f[2][4], f[2][1] + 4) = max(0, 0+4) = 4
• j = 5: f[3][5] = max(f[2][5], f[2][2] + 4) = max(3, 0+4) = 4
• j = 6: f[3][6] = max(f[2][6], f[2][3] + 4) = max(3, 0+4) = 4
• j = 7: f[3][7] = max(f[2][7], f[2][4] + 4) = max(3, 0+4) = 4
• j = 8: f[3][8] = max(f[2][8], f[2][5] + 4) = max(3, 3+4) = 7

    Budget: 0  1  2  3  4  5  6  7  8
Stock 0:    0  0  0  0  0  0  0  0  0
Stock 1:    0  0  0  0  0  3  3  3  3
Stock 2:    0  0  0  0  0  3  3  3  3
Stock 3:    0  0  0  4  4  4  4  4  7

Result: The maximum profit is f[3][8] = 7

This means we should buy Stock 0 (cost 5, profit 3) and Stock 2 (cost 3, profit 4) for a total cost of 8 and total profit of 7.

The key insight: at each step, we're asking "Given this budget and these stocks available, should I buy the current stock or not?" The DP table helps us make optimal decisions by storing the best results for all subproblems.

Solution Implementation

Time and Space Complexity

The time complexity of this code is O(n × budget), where n is the length of the present array (which equals the length of the future array). This is because we have two nested loops: the outer loop iterates through all items (from index 1 to n), and the inner loop iterates through all possible budget values (from 0 to budget). Each iteration performs constant time operations, resulting in n × (budget + 1) total operations.

The space complexity is O(n × budget) as well. This is due to the 2D dynamic programming table f that we create with dimensions (len(present) + 1) × (budget + 1), which equals (n + 1) × (budget + 1). This table stores all intermediate results for the dynamic programming solution, where f[i][j] represents the maximum profit achievable using the first i items with a budget of j.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Including Unprofitable Stocks in the Knapsack

One common pitfall is forgetting to check whether a stock is actually profitable before considering it for purchase. The code correctly handles this with the condition future_price > current_price, but developers often miss this check and include stocks with negative or zero profit.

Incorrect approach:

# Missing profit check - might include stocks that lose money
if current_budget >= current_price:
    profit_from_current = future_price - current_price  # Could be negative!
    dp[i][current_budget] = max(
        dp[i][current_budget],
        dp[i - 1][current_budget - current_price] + profit_from_current
    )

Correct approach:

# Only consider stocks that will make a profit
if current_budget >= current_price and future_price > current_price:
    profit_from_current = future_price - current_price
    dp[i][current_budget] = max(
        dp[i][current_budget],
        dp[i - 1][current_budget - current_price] + profit_from_current
    )

2. Off-by-One Errors in Array Indexing

When using a DP table with dimensions (n+1) × (budget+1), it's easy to confuse the indices. The DP table uses 1-based indexing for stocks while the input arrays use 0-based indexing.

Incorrect approach:

# Wrong indexing - using i directly for present/future arrays
for i in range(1, n + 1):
    current_price = present[i]  # IndexError!
    future_price = future[i]    # IndexError!

Correct approach:

# Proper indexing - subtract 1 when accessing the input arrays
for i in range(1, n + 1):
    current_price = present[i - 1]
    future_price = future[i - 1]

3. Space Optimization Pitfall

While optimizing space from O(n × budget) to O(budget) using a 1D array, a common mistake is updating the array from left to right, which causes values to be overwritten before they're used.

Incorrect space-optimized approach:

# Wrong: iterating forward overwrites values we still need
dp = [0] * (budget + 1)
for i in range(n):
    for j in range(budget + 1):  # Forward iteration - WRONG!
        if j >= present[i] and future[i] > present[i]:
            dp[j] = max(dp[j], dp[j - present[i]] + future[i] - present[i])

Correct space-optimized approach:

# Correct: iterate backwards to preserve previous values
dp = [0] * (budget + 1)
for i in range(n):
    for j in range(budget, present[i] - 1, -1):  # Backward iteration
        if future[i] > present[i]:
            dp[j] = max(dp[j], dp[j - present[i]] + future[i] - present[i])

The backward iteration ensures that when we compute dp[j], the value dp[j - present[i]] still contains the result from the previous iteration (without the current stock), not the updated value from the current iteration.