Problem

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.

Examples

Example 1:

1
2
3
4
5
6
7

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 0th, 3rd, and 4th 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:

1
2
3
4
5

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 2nd stock, and make a profit of 10 - 5 = 5.
It can be shown that the maximum profit you can make is 5.

Example 3:

1
2
3
4
5

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 1st 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

Solution

Method 1 – Dynamic Programming (0/1 Knapsack)

Intuition

We treat each stock as an item with a cost (present[i]) and a value (future[i] - present[i]). The goal is to select a subset of stocks such that the total cost does not exceed the budget and the total profit is maximized.

Approach

  1. Initialize a DP array dp of size budget + 1 with all zeros, where dp[j] is the max profit achievable with budget j.
  2. For each stock:
    • Compute its cost and profit.
    • For each possible budget from high to low (to avoid using the same stock multiple times), update dp[j] as the max of its current value and dp[j - cost] + profit if j >= cost.
  3. The answer is the maximum value in dp.

Code

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

class Solution {
public:
    int maximumProfit(vector<int>& present, vector<int>& future, int budget) {
        int n = present.size();
        vector<int> dp(budget + 1, 0);
        for (int i = 0; i < n; ++i) {
            int cost = present[i], profit = future[i] - present[i];
            for (int j = budget; j >= cost; --j) {
                dp[j] = max(dp[j], dp[j - cost] + profit);
            }
        }
        return *max_element(dp.begin(), dp.end());
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

func maximumProfit(present []int, future []int, budget int) int {
    n := len(present)
    dp := make([]int, budget+1)
    for i := 0; i < n; i++ {
        cost, profit := present[i], future[i]-present[i]
        for j := budget; j >= cost; j-- {
            if dp[j-cost]+profit > dp[j] {
                dp[j] = dp[j-cost] + profit
            }
        }
    }
    ans := 0
    for _, v := range dp {
        if v > ans {
            ans = v
        }
    }
    return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution {
    public int maximumProfit(int[] present, int[] future, int budget) {
        int n = present.length;
        int[] dp = new int[budget + 1];
        for (int i = 0; i < n; i++) {
            int cost = present[i], profit = future[i] - present[i];
            for (int j = budget; j >= cost; j--) {
                dp[j] = Math.max(dp[j], dp[j - cost] + profit);
            }
        }
        int ans = 0;
        for (int v : dp) ans = Math.max(ans, v);
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution {
    fun maximumProfit(present: IntArray, future: IntArray, budget: Int): Int {
        val n = present.size
        val dp = IntArray(budget + 1)
        for (i in 0 until n) {
            val cost = present[i]
            val profit = future[i] - present[i]
            for (j in budget downTo cost) {
                dp[j] = maxOf(dp[j], dp[j - cost] + profit)
            }
        }
        return dp.maxOrNull() ?: 0
    }
}
1
2
3
4
5
6
7
8
9

class Solution:
    def maximumProfit(self, present: list[int], future: list[int], budget: int) -> int:
        n = len(present)
        dp = [0] * (budget + 1)
        for i in range(n):
            cost, profit = present[i], future[i] - present[i]
            for j in range(budget, cost - 1, -1):
                dp[j] = max(dp[j], dp[j - cost] + profit)
        return max(dp)
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

impl Solution {
    pub fn maximum_profit(present: Vec<i32>, future: Vec<i32>, budget: i32) -> i32 {
        let n = present.len();
        let mut dp = vec![0; (budget + 1) as usize];
        for i in 0..n {
            let cost = present[i] as usize;
            let profit = future[i] - present[i];
            for j in (cost..=budget as usize).rev() {
                dp[j] = dp[j].max(dp[j - cost] + profit);
            }
        }
        *dp.iter().max().unwrap()
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution {
    maximumProfit(present: number[], future: number[], budget: number): number {
        const n = present.length;
        const dp = Array(budget + 1).fill(0);
        for (let i = 0; i < n; i++) {
            const cost = present[i], profit = future[i] - present[i];
            for (let j = budget; j >= cost; j--) {
                dp[j] = Math.max(dp[j], dp[j - cost] + profit);
            }
        }
        return Math.max(...dp);
    }
}

Complexity

  • ⏰ Time complexity: O(n * budget), since for each stock, we iterate over all possible budgets.
  • 🧺 Space complexity: O(budget), for the DP array.