# 2291. Maximum Profit From Trading Stocks

## Approach 1: 2D DP

• Time: $O(n\cdot\texttt{budget})$
• Space: $O(n\cdot\texttt{budget})$
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 class Solution { public: int maximumProfit(vector& present, vector& future, int budget) { const int n = present.size(); // dp[i][j] := max profit of buying present[0..i) with j budget vector> dp(n + 1, vector(budget + 1)); for (int i = 1; i <= n; ++i) { const int profit = future[i - 1] - present[i - 1]; for (int j = 0; j <= budget; ++j) if (j < present[i - 1]) dp[i][j] = dp[i - 1][j]; else dp[i][j] = max(dp[i - 1][j], profit + dp[i - 1][j - present[i - 1]]); } return dp[n][budget]; } }; 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 class Solution { public int maximumProfit(int[] present, int[] future, int budget) { final int n = present.length; // dp[i][j] := max profit of buying present[0..i) with j budget int[][] dp = new int[n + 1][budget + 1]; for (int i = 1; i <= n; ++i) { final int profit = future[i - 1] - present[i - 1]; for (int j = 0; j <= budget; ++j) if (j < present[i - 1]) dp[i][j] = dp[i - 1][j]; else dp[i][j] = Math.max(dp[i - 1][j], profit + dp[i - 1][j - present[i - 1]]); } return dp[n][budget]; } } 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 class Solution: def maximumProfit(self, present: List[int], future: List[int], budget: int) -> int: n = len(present) # dp[i][j] := max profit of buying present[0..i) with j budget dp = [[0] * (budget + 1) for _ in range(n + 1)] for i in range(1, n + 1): profit = future[i - 1] - present[i - 1] for j in range(budget + 1): if j < present[i - 1]: dp[i][j] = dp[i - 1][j] else: dp[i][j] = max(dp[i - 1][j], profit + dp[i - 1][j - present[i - 1]]) return dp[n][budget] 

## Approach 2: 1D DP

• Time: $O(n\cdot\texttt{budget})$
• Space: $O(\texttt{budget})$
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 class Solution { public: int maximumProfit(vector& present, vector& future, int budget) { const int n = present.size(); // dp[i] := max profit of buying present so far with i budget vector dp(budget + 1); for (int i = 0; i < n; ++i) for (int j = budget; j >= present[i]; --j) dp[j] = max(dp[j], future[i] - present[i] + dp[j - present[i]]); return dp[budget]; } }; 
  1 2 3 4 5 6 7 8 9 10 11 12 13 class Solution { public int maximumProfit(int[] present, int[] future, int budget) { final int n = present.length; // dp[i] := max profit of buying present so far with i budget int[] dp = new int[budget + 1]; for (int i = 0; i < n; ++i) for (int j = budget; j >= present[i]; --j) dp[j] = Math.max(dp[j], future[i] - present[i] + dp[j - present[i]]); return dp[budget]; } } 
  1 2 3 4 5 6 7 8 9 10 11 class Solution: def maximumProfit(self, present: List[int], future: List[int], budget: int) -> int: n = len(present) # dp[i] := max profit of buying present so far with i budget dp = [0] * (budget + 1) for p, f in zip(present, future): for j in range(budget, p - 1, -1): dp[j] = max(dp[j], f - p + dp[j - p]) return dp[budget]