# 2291. Maximum Profit From Trading Stocks
###### tags: `Leetcode` `Medium` `Dynamic Programming` `Knapsack problem`
Link: https://leetcode.com/problems/maximum-profit-from-trading-stocks/
## 思路
典型背包问题
## Code
java

class Solution {
    public int maximumProfit(int[] present, int[] future, int budget) {
        int n = present.length;
        int[][] dp = new int[n+1][budget+1];
        for(int i=1; i<=n; i++){
            for(int j=0; j<=budget; j++){
                dp[i][j] = Math.max(dp[i][j], dp[i-1][j]);
                if(j>=present[i-1]) dp[i][j] = Math.max(dp[i][j], dp[i-1][j-present[i-1]]+future[i-1]-present[i-1]);
            }
        }
        return dp[n][budget];
    }
}

c++

class Solution {
public:
    int maximumProfit(vector<int>& present, vector<int>& future, int budget) {
        int n = present.size();
        auto dp = vector<vector<int>>(n+1, vector<int>(budget+1));
        for(int i=1; i<=n; i++){
            for(int j=0; j<=budget; j++){
                dp[i][j] = dp[i-1][j];
                if(j>=present[i-1]) dp[i][j] = max(dp[i][j], dp[i-1][j-present[i-1]]+future[i-1]-present[i-1]);
            }
        }
        int ans = 0;
        for(int i=0; i<=budget; i++) ans = max(ans, dp[n][i]);
        return ans;
    }
};