Maximum Profit From Trading Stocks — LeetCode 2291 Python Solution
MediumLeetCode PremiumArrayDynamic Programming
- Problem
- #2291
- Pattern
- Dynamic Programming
- Reading time
- 2 min
- Source
- leetcode.com
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.
Example
- 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:
Python solution
Python
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]Complexity
| Measure | Complexity |
|---|---|
| Time | O(n \times \textit{budget}) |
| Space | O(n \times \textit{budget}) auxiliary |
Pattern: Dynamic Programming
Define a state, write the transition, and stop recomputing the same subproblem. LeetCode 2291. Maximum Profit From Trading Stocks is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Dynamic Programming.
The dynamic programming guide has the Python template for the pattern and the 481 LeetCode problems that use it.
Related problems
Frequently asked questions
- How hard is LeetCode 2291. Maximum Profit From Trading Stocks?
- LeetCode 2291. Maximum Profit From Trading Stocks is rated Medium on LeetCode.
- What is the time complexity of LeetCode 2291. Maximum Profit From Trading Stocks?
- The Python solution on this page runs in O(n \times \textit{budget}).
- What is the space complexity of LeetCode 2291. Maximum Profit From Trading Stocks?
- The Python solution on this page uses O(n \times \textit{budget}) auxiliary space.
- What topics does LeetCode 2291. Maximum Profit From Trading Stocks cover?
- LeetCode 2291. Maximum Profit From Trading Stocks is tagged Array and Dynamic Programming on LeetCode.
- Is LeetCode 2291. Maximum Profit From Trading Stocks a premium problem?
- Yes. LeetCode 2291. Maximum Profit From Trading Stocks is a LeetCode Premium problem, so the full statement and test cases require a paid LeetCode subscription.