2291. Maximum Profit From Trading Stocks

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.

class Solution {
    int dp[1001][1001];
    int helper(vector<int>& c, vector<int>& p, int b, int i) {
        if(i == c.size()) return 0;
        if(dp[b][i] != -1) return dp[b][i];
        dp[b][i] = helper(c, p, b, i + 1);
        if(b >= c[i] and c[i] < p[i])
            dp[b][i] = max(dp[b][i], p[i] - c[i] + helper(c, p, b - c[i], i + 1));
        return dp[b][i];
    }
public:
    int maximumProfit(vector<int>& present, vector<int>& future, int budget) {
        memset(dp, -1, sizeof dp);
        return helper(present, future, budget, 0);
    }
};