2291. Maximum Profit From Trading Stocks

1. Description

You are given two 0-indexed 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.

2. Example

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.

3. Constraints

• n == present.length == future.length
• 1 <= n <= 1000
• 0 <= present[i], future[i] <= 100
• 0 <= budget <= 1000

4. Solutions

Dynamic Programming

n = present.size(), b = budget
Time complexity: O(nb)
Space complexity: O(b)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

class Solution {
public:
    int maximumProfit(vector<int> &present, vector<int> &future, int budget) {
        const int n = present.size();
        vector<int> profits(budget + 1, 0);
        for (int i = 0; i < n; ++i) {
            int cost = present[i];
            int profit = future[i] - cost;

            for (int j = budget; j >= cost; --j) {
                profits[j] = max(profits[j], profits[j - cost] + profit);
            }
        }

        return profits.back();
    }
};