Maximum Profit From Trading Stocks solution and explanation
3 more videos on this problem
2291. Maximum Profit From Trading Stocks (Leetcode Medium)Programming Live with Larry · 14:12 · 3K views
2291. Maximum Profit From Trading StocksClayton Wong · 59:17 · 507 views
2291. Maximum Profit From Trading StocksJust Coding, with Jie · 10:19 · 357 views
Leetcode 2291. Maximum Profit From Trading Stocks (01 knapsack)LetsCode · 8:34 · 326 views
The problem
You are given two 0-indexed integer arrays of the same length present and future where present[i] is the current price of the ith stock and future[i] is the price of the ith stock a year in the future. You may buy each stock at most once. You are also given an integer budget representing the amount of money you currently have.
Return the maximum amount of profit you can make.
Example 1:
Input: present = [5,4,6,2,3], future = [8,5,4,3,5], budget = 10 Output: 6 Explanation: One possible way to maximize your profit is to: Buy the 0th, 3rd, and 4th stocks for a total of 5 + 2 + 3 = 10. Next year, sell all three stocks for a total of 8 + 3 + 5 = 16. The profit you made is 16 - 10 = 6. It can be shown that the maximum profit you can make is 6.
Example 2:
Input: present = [2,2,5], future = [3,4,10], budget = 6 Output: 5 Explanation: The only possible way to maximize your profit is to: Buy the 2nd stock, and make a profit of 10 - 5 = 5. It can be shown that the maximum profit you can make is 5.
Example 3:
Input: present = [3,3,12], future = [0,3,15], budget = 10 Output: 0 Explanation: One possible way to maximize your profit is to: Buy the 1st stock, and make a profit of 3 - 3 = 0. It can be shown that the maximum profit you can make is 0.
Constraints:
n == present.length == future.length1 <= n <= 10000 <= present[i], future[i] <= 1000 <= budget <= 1000
Approach overview
Problem Overview: You are given two arrays: present and future. Buying stock i costs present[i] today and can be sold later for future[i]. With a limited budget, choose which stocks to buy to maximize total profit (future[i] - present[i]). Each stock can be purchased at most once.
The key observation: buying a stock only makes sense if it generates positive profit. After converting each stock into cost and profit, the problem becomes a classic 0/1 knapsack optimization.
Approach 1: Dynamic Programming (0/1 Knapsack) (Time: O(n * budget), Space: O(n * budget))
Treat each stock as an item where the weight is present[i] (the money spent) and the value is max(0, future[i] - present[i]) (the profit). Build a DP table dp[i][b] representing the maximum profit using the first i stocks with budget b. For every stock, decide whether to skip it or buy it if the remaining budget allows. The transition becomes dp[i][b] = max(dp[i-1][b], dp[i-1][b-present[i]] + profit). This approach explicitly models all choices and is easy to reason about when learning Dynamic Programming patterns.
Iteration runs through all stocks and every possible budget value, which results in O(n * budget) time. The full DP table stores states for each item and budget combination, requiring O(n * budget) memory.
Approach 2: Dynamic Programming (Space Optimization) (Time: O(n * budget), Space: O(budget))
The DP transition only depends on the previous row, so the 2D table can be compressed into a 1D array. Maintain dp[b] as the best profit achievable with budget b. For each stock, iterate the budget backwards from budget down to present[i]. Backward iteration prevents reusing the same stock multiple times, preserving the 0/1 constraint.
This reduces memory from O(n * budget) to O(budget) while keeping the same O(n * budget) runtime. The pattern appears frequently in problems that combine Array iteration with Dynamic Programming, especially knapsack-style optimizations.
Recommended for interviews: Start by explaining the knapsack transformation: cost equals purchase price and value equals profit. Interviewers expect the optimized 1D DP solution because it demonstrates strong understanding of state transitions and memory optimization. Mentioning the full 2D DP first shows you understand the recurrence before reducing space.
Approach 1: Dynamic Programming
We define f[i][j] to represent the maximum profit when considering the first i stocks with a budget of j. The answer is f[n][budget].
For the i-th stock, we have two choices:
- Do not buy it, then
f[i][j] = f[i - 1][j]; - Buy it, then
f[i][j] = f[i - 1][j - present[i]] + future[i] - present[i].
Finally, return f[n][budget].
The time complexity is O(n times budget), and the space complexity is O(n times budget). Where n is the length of the array.
class Solution:
def maximumProfit(self, present: List[int], future: List[int], budget: int) -> int:
f = [[0] * (budget + 1) for _ in range(len(present) + 1)]
for i, w in enumerate(present, 1):
for j in range(budget + 1):
f[i][j] = f[i - 1][j]
if j >= w and future[i - 1] > w:
f[i][j] = max(f[i][j], f[i - 1][j - w] + future[i - 1] - w)
return f[-1][-1]class Solution {
public int maximumProfit(int[] present, int[] future, int budget) {
int n = present.length;
int[][] f = new int[n + 1][budget + 1];
for (int i = 1; i <= n; ++i) {
for (int j = 0; j <= budget; ++j) {
f[i][j] = f[i - 1][j];
if (j >= present[i - 1]) {
f[i][j] = Math.max(
f[i][j], f[i - 1][j - present[i - 1]] + future[i - 1] - present[i - 1]);
}
}
}
return f[n][budget];
}
}class Solution {
public:
int maximumProfit(vector<int>& present, vector<int>& future, int budget) {
int n = present.size();
int f[n + 1][budget + 1];
memset(f, 0, sizeof f);
for (int i = 1; i <= n; ++i) {
for (int j = 0; j <= budget; ++j) {
f[i][j] = f[i - 1][j];
if (j >= present[i - 1]) {
f[i][j] = max(f[i][j], f[i - 1][j - present[i - 1]] + future[i - 1] - present[i - 1]);
}
}
}
return f[n][budget];
}
};function maximumProfit(present: number[], future: number[], budget: number): number {
const f = new Array(budget + 1).fill(0);
for (let i = 0; i < present.length; ++i) {
const [a, b] = [present[i], future[i]];
for (let j = budget; j >= a; --j) {
f[j] = Math.max(f[j], f[j - a] + b - a);
}
}
return f[budget];
}func maximumProfit(present []int, future []int, budget int) int {
n := len(present)
f := make([][]int, n+1)
for i := range f {
f[i] = make([]int, budget+1)
}
for i := 1; i <= n; i++ {
for j := 0; j <= budget; j++ {
f[i][j] = f[i-1][j]
if j >= present[i-1] {
f[i][j] = max(f[i][j], f[i-1][j-present[i-1]]+future[i-1]-present[i-1])
}
}
}
return f[n][budget]
}Approach 2: Dynamic Programming (Space Optimization)
We can observe that for each row, we only need the values from the previous row, so we can optimize the space complexity to O(budget).
class Solution:
def maximumProfit(self, present: List[int], future: List[int], budget: int) -> int:
f = [0] * (budget + 1)
for a, b in zip(present, future):
for j in range(budget, a - 1, -1):
f[j] = max(f[j], f[j - a] + b - a)
return f[-1]class Solution {
public int maximumProfit(int[] present, int[] future, int budget) {
int n = present.length;
int[] f = new int[budget + 1];
for (int i = 0; i < n; ++i) {
int a = present[i], b = future[i];
for (int j = budget; j >= a; --j) {
f[j] = Math.max(f[j], f[j - a] + b - a);
}
}
return f[budget];
}
}class Solution {
public:
int maximumProfit(vector<int>& present, vector<int>& future, int budget) {
int n = present.size();
int f[budget + 1];
memset(f, 0, sizeof f);
for (int i = 0; i < n; ++i) {
int a = present[i], b = future[i];
for (int j = budget; j >= a; --j) {
f[j] = max(f[j], f[j - a] + b - a);
}
}
return f[budget];
}
};func maximumProfit(present []int, future []int, budget int) int {
f := make([]int, budget+1)
for i, a := range present {
for j := budget; j >= a; j-- {
f[j] = max(f[j], f[j-a]+future[i]-a)
}
}
return f[budget]
}Complexity comparison
| Approach | Complexity |
|---|---|
| Dynamic Programming | – |
| Dynamic Programming (Space Optimization) | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Dynamic Programming (2D Knapsack) | O(n * budget) | O(n * budget) | Best for understanding the full DP state transition and debugging logic |
| Dynamic Programming (Space Optimized) | O(n * budget) | O(budget) | Preferred in interviews and production when memory efficiency matters |
Frequently asked questions
Is Maximum Profit From Trading Stocks easy or hard?
Maximum Profit From Trading Stocks is typically classified as Medium difficulty. The main challenge is recognizing that the problem reduces to a 0/1 Knapsack Dynamic Programming formulation.
Maximum Profit From Trading Stocks Python/Java solution
Implement a knapsack DP where dp[b] represents the best profit for budget b. For each stock, compute profit = future[i] - present[i] and update the DP array from budget down to present[i]. The same logic works in Python, Java, C++, Go, and TypeScript.
How to solve Maximum Profit From Trading Stocks in O(n * budget)?
Convert each stock into a knapsack item with weight equal to its present price and value equal to its profit. Use a 1D DP array where dp[b] stores the maximum profit achievable with budget b. Iterate stocks and update the DP array backward from budget to present[i].
What is the best approach for Maximum Profit From Trading Stocks?
The most effective approach is Dynamic Programming using the 0/1 Knapsack pattern. Each stock has a cost (present price) and profit (future minus present price). A space‑optimized DP solution computes the maximum profit for every budget value in O(n * budget) time and O(budget) space.
Is Maximum Profit From Trading Stocks asked at Google/Amazon/Meta?
Knapsack-style Dynamic Programming problems frequently appear in interviews at companies like Amazon, Google, and Meta. Variations of budget optimization and resource allocation are common technical interview patterns.
What data structure is used in Maximum Profit From Trading Stocks?
The solution mainly relies on arrays combined with Dynamic Programming. A DP array stores the maximum achievable profit for each budget value while iterating through the stocks.
What is the time complexity of Maximum Profit From Trading Stocks?
The optimal Dynamic Programming solution runs in O(n * budget) time, where n is the number of stocks and budget is the available money. Each stock is processed once while iterating through all possible budget values.