Welcome to Subscribe On Youtube
2291. Maximum Profit From Trading Stocks
Description
You are given two 0indexed integer arrays of the same length present
and future
where present[i]
is the current price of the i^{th}
stock and future[i]
is the price of the i^{th}
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 0^{th}, 3^{rd}, and 4^{th} 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 2^{nd} 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 1^{st} 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
Solutions

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]; } };

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]

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[i1][j] if j >= present[i1] { f[i][j] = max(f[i][j], f[i1][jpresent[i1]]+future[i1]present[i1]) } } } 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]; }