LeetCode 2291 - Maximum Profit From Trading Stocks

LeetCode Problem 2291

Difficulty: 🟡 Medium
Topics: Array, Dynamic Programming

Solution

Problem Understanding

The problem gives us two arrays, present and future, where each index represents a stock. The value present[i] is the price of buying the i-th stock today, while future[i] is the price at which the same stock can be sold one year later.

We are also given a limited budget, which represents how much money we can spend today purchasing stocks. Each stock may be purchased at most once, meaning this is a selection problem where we either buy a stock or skip it.

The goal is to maximize profit, not total future value. If we buy a stock at price present[i] and later sell it at future[i], the profit contribution is:

$$future[i] - present[i]$$

We may choose any subset of stocks, provided that the total purchase cost does not exceed budget. The task is to return the maximum total profit achievable.

An important observation is that stocks with non-positive profit are never useful. If:

$$future[i] \le present[i]$$

then buying the stock gives zero or negative profit, so it never improves the answer. We can safely ignore such stocks.

The constraints tell us a lot about the expected solution:

• n <= 1000
• budget <= 1000

A brute force search over all subsets would require checking up to:

$$2^{1000}$$

possible combinations, which is completely infeasible.

However, the relatively small budget strongly suggests a dynamic programming over budget approach. Since both n and budget are at most 1000, an O(n × budget) solution is practical.

Some important edge cases to keep in mind are:

• budget = 0, where no purchases can be made.
• All stocks have negative or zero profit, meaning the answer should be 0.
• A stock costs more than the entire budget, meaning it cannot be purchased.
• Multiple profitable stocks exist, but buying the individually best stock is not globally optimal. We must consider combinations.
• Stocks with present[i] = 0, which can be bought for free and may create profit without affecting budget.

Approaches

Brute Force Approach

A straightforward solution is to try every possible subset of stocks.

For each stock, we have two choices:

1. Buy the stock.
2. Skip the stock.

This naturally forms a binary decision tree. For every subset, we calculate:

• The total buying cost.
• The total profit.

If the total cost does not exceed the budget, we compare the profit against the best answer seen so far.

This approach is correct because it exhaustively explores every valid combination of purchases, guaranteeing that the maximum profit is found.

However, the number of subsets grows exponentially:

$$2^n$$

With n = 1000, this is impossible to compute within time limits.

Optimal Approach, 0/1 Knapsack Dynamic Programming

The key insight is that this problem is actually a 0/1 Knapsack problem.

Each stock behaves like an item:

• Weight (cost) = present[i]
• Value (profit) = future[i] - present[i]

We want to maximize total value while staying within a fixed budget.

Since each stock can only be bought once, this is specifically a 0/1 knapsack, not an unbounded knapsack.

We define:

dp[b] = maximum profit achievable using budget b

For each profitable stock, we iterate the budget backward so that each stock is used at most once.

Backward iteration is critical. If we iterated forward, the same stock could accidentally be counted multiple times, turning the problem into an unbounded knapsack.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(2ⁿ)	O(n)	Tries every subset of stocks
Optimal	O(n × budget)	O(budget)	Uses 0/1 knapsack dynamic programming

Algorithm Walkthrough

Optimal Dynamic Programming Algorithm

1. Initialize the DP array

Create an array dp of size budget + 1.

dp[b] will store the maximum profit achievable using at most b dollars.

Initially, all values are 0 because making no purchases always gives zero profit. 2. Process each stock

For every stock i:

• Compute:

cost = present[i]

profit = future[i] - present[i]

If profit <= 0, skip the stock because buying it cannot improve the answer. 3. Update the DP array backward

For every budget value from budget down to cost:

Check whether buying this stock improves profit:

dp[b] = max(dp[b], dp[b - cost] + profit)

Here:

• dp[b] means skipping the stock.
• dp[b - cost] + profit means buying it.

We choose whichever gives higher profit. 4. Continue for all stocks

Repeat this update process for every profitable stock. 5. Return the answer

The final answer is:

dp[budget]

which represents the maximum profit achievable within the available budget.

Why it works

The algorithm works because it maintains an invariant:

After processing the first i stocks, dp[b] stores the maximum profit achievable using those stocks with budget b.

For each stock, we consider both possibilities, buying or skipping it. Since we iterate the budget backward, a stock contributes at most once to any state transition. Thus, every valid combination is considered exactly once, which guarantees that the optimal solution is found.

Python Solution

from typing import List

class Solution:
    def maximumProfit(self, present: List[int], future: List[int], budget: int) -> int:
        dp = [0] * (budget + 1)

        for current_price, future_price in zip(present, future):
            profit = future_price - current_price

            # Ignore non-profitable stocks
            if profit <= 0:
                continue

            # 0/1 knapsack update
            for current_budget in range(budget, current_price - 1, -1):
                dp[current_budget] = max(
                    dp[current_budget],
                    dp[current_budget - current_price] + profit
                )

        return dp[budget]

Implementation Explanation

The solution begins by creating a one-dimensional DP array of size budget + 1. Each index represents a possible spending limit, and the stored value is the best profit achievable within that limit.

We then iterate through every stock using zip(present, future) so that the buy price and future price are processed together.

For each stock, we compute its profit:

profit = future_price - current_price

If the profit is not positive, the stock is skipped because buying it cannot increase the total result.

For profitable stocks, we perform the standard 0/1 knapsack transition. The loop iterates backward through the budget range:

for current_budget in range(budget, current_price - 1, -1):

This backward traversal ensures the stock is used at most once. If we iterated forward, the same stock could contribute multiple times during a single iteration.

The transition:

dp[current_budget] = max(
    dp[current_budget],
    dp[current_budget - current_price] + profit
)

compares two choices:

• Skip the stock and keep the existing value.
• Buy the stock and add its profit to the best previously achievable state.

After all stocks are processed, dp[budget] contains the optimal profit.

Go Solution

func maximumProfit(present []int, future []int, budget int) int {
	dp := make([]int, budget+1)

	for i := 0; i < len(present); i++ {
		cost := present[i]
		profit := future[i] - present[i]

		// Ignore non-profitable stocks
		if profit <= 0 {
			continue
		}

		// 0/1 knapsack update
		for currentBudget := budget; currentBudget >= cost; currentBudget-- {
			candidate := dp[currentBudget-cost] + profit
			if candidate > dp[currentBudget] {
				dp[currentBudget] = candidate
			}
		}
	}

	return dp[budget]
}

Go Specific Notes

The Go implementation follows the exact same dynamic programming strategy as the Python version.

Instead of Python lists, Go uses a slice:

dp := make([]int, budget+1)

Since Go does not have a built-in max function for integers, we manually compare values using an if statement.

Integer overflow is not a concern here because:

• future[i] <= 100
• n <= 1000

The maximum possible profit remains comfortably within Go's int range.

Nil slices are also not an issue because LeetCode guarantees valid input arrays of equal length.

Worked Examples

Example 1

present = [5,4,6,2,3]
future = [8,5,4,3,5]
budget = 10

Profits:

Stock	Cost	Future	Profit
0	5	8	3
1	4	5	1
2	6	4	-2
3	2	3	1
4	3	5	2

Ignore stock 2.

Initial DP:

Budget	0	1	2	3	4	5	6	7	8	9	10
Profit	0	0	0	0	0	0	0	0	0	0	0

After stock 0 (cost=5, profit=3):

Budget	0	1	2	3	4	5	6	7	8	9	10
Profit	0	0	0	0	0	3	3	3	3	3	3

After stock 1 (cost=4, profit=1):

Budget	0	1	2	3	4	5	6	7	8	9	10
Profit	0	0	0	0	1	3	3	3	3	4	4

After stock 3 (cost=2, profit=1):

Budget	0	1	2	3	4	5	6	7	8	9	10
Profit	0	0	1	1	1	3	3	4	4	4	4

After stock 4 (cost=3, profit=2):

Budget	0	1	2	3	4	5	6	7	8	9	10
Profit	0	0	1	2	2	3	3	5	5	5	6

Final answer:

6

Example 2

present = [2,2,5]
future = [3,4,10]
budget = 6

Profits:

Stock	Cost	Profit
0	2	1
1	2	2
2	5	5

The DP eventually determines:

• Buying stock 2 gives profit 5
• Buying stocks 0 + 1 gives profit 3

Maximum profit:

5

Example 3

present = [3,3,12]
future = [0,3,15]
budget = 10

Profits:

Stock	Cost	Profit
0	3	-3
1	3	0
2	12	3

• Stock 0 loses money.
• Stock 1 gives no gain.
• Stock 2 exceeds budget.

No profitable transaction is possible.

Final answer:

0

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n × budget)	We process every stock and iterate through all budget values
Space	O(budget)	Only a one-dimensional DP array is used

The time complexity comes from the nested loops. For each of the n stocks, we potentially iterate through all budget values from budget down to cost.

The space complexity is efficient because we compress the usual two-dimensional knapsack DP into a single array. Since updates happen backward, we do not need to store previous rows separately.

Test Cases

sol = Solution()

# Provided examples
assert sol.maximumProfit([5,4,6,2,3], [8,5,4,3,5], 10) == 6  # example 1
assert sol.maximumProfit([2,2,5], [3,4,10], 6) == 5  # example 2
assert sol.maximumProfit([3,3,12], [0,3,15], 10) == 0  # example 3

# Zero budget
assert sol.maximumProfit([1,2,3], [5,6,7], 0) == 0  # cannot buy anything

# No profitable stocks
assert sol.maximumProfit([5,5,5], [1,2,3], 10) == 0  # all negative profits

# Exact budget usage
assert sol.maximumProfit([2,3,5], [5,7,8], 10) == 10  # buy all stocks

# Best combination beats single stock
assert sol.maximumProfit([4,5,6], [7,9,10], 9) == 7  # buy first two

# Stock exceeds budget
assert sol.maximumProfit([100], [200], 50) == 0  # unaffordable stock

# Free profitable stock
assert sol.maximumProfit([0,5], [3,10], 5) == 8  # free profit + buy second

# Single stock profitable
assert sol.maximumProfit([5], [10], 5) == 5  # simple case

# Single stock unprofitable
assert sol.maximumProfit([5], [4], 5) == 0  # should skip

# Large budget but poor choices
assert sol.maximumProfit([2,3,4], [2,3,4], 100) == 0  # zero profits

Test Summary

Test	Why
Example 1	Verifies normal multi-stock optimization
Example 2	Confirms single expensive stock is optimal
Example 3	Ensures result is zero when no profitable option exists
Zero budget	Verifies inability to buy any stock
No profitable stocks	Ensures bad trades are skipped
Exact budget usage	Confirms full budget utilization works
Best combination beats single stock	Validates true knapsack behavior
Stock exceeds budget	Ensures unaffordable stocks are ignored
Free profitable stock	Tests zero-cost stock handling
Single profitable stock	Smallest profitable input
Single unprofitable stock	Smallest non-profitable input
Large budget but poor choices	Confirms zero-profit handling

Edge Cases

Budget is zero

When budget = 0, no stock can be purchased regardless of profitability. A buggy implementation might accidentally include zero-cost stocks incorrectly or attempt invalid indexing.

The implementation handles this naturally because the DP array has size 1, and budget loops never execute unless a stock cost is 0. The answer remains correctly initialized to 0.

All stocks are non-profitable

If every stock has:

future[i] <= present[i]

then buying any stock either loses money or produces no gain.

A naive implementation might still include zero-profit or negative-profit trades, wasting budget and reducing the result. Our implementation explicitly skips these stocks:

if profit <= 0:
    continue

This guarantees only beneficial trades are considered.

A stock costs more than the budget

Some stocks may have strong profit but still be impossible to afford.

For example:

present = [20]
future = [50]
budget = 10

The inner loop:

range(budget, cost - 1, -1)

never executes if cost > budget, meaning the stock is automatically ignored without special-case logic.

Choosing combinations over greedy picks

A greedy strategy may fail by always choosing the individually highest-profit stock.

For example:

present = [4, 5, 6]
future = [7, 9, 10]
budget = 9

The best single stock gives profit 4, but buying the first two stocks gives:

3 + 4 = 7

The dynamic programming approach correctly evaluates all feasible combinations and avoids this common mistake.