Skip to main content
Talentd

Maximum Profit From Trading Stocks - Solution & Explanation

MediumPremiumFree on FleetCodeArrayDynamic Programming8 min readAsked at: Amazon, Oracle, BlackRock +2
Practice this problem

Problem Statement

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.length
  • 1 <= n <= 1000
  • 0 <= present[i], future[i] <= 100
  • 0 <= 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.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

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).

Code

PythonJavaC++Go

Python

Java

C++

Go

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Dynamic Programming—
Dynamic Programming (Space Optimization)—

Detailed Complexity Analysis

ApproachTimeSpaceWhen 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

Video Solution

2291. Maximum Profit From Trading Stocks (Leetcode Medium) • Programming Live with Larry • 3,278 views views

Watch 3 more video solutions →

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.

Ready to solve this problem?

Practice Maximum Profit From Trading Stocks with our built-in code editor and test cases.

Practice on FleetCode
Previous

Best Time to Buy and Sell Stock

Next

Best Time to Buy and Sell Stock II