# Maximum Profit from Trading Stocks with Discounts
**Difficulty:** HARD
[External](https://leetcode.com/problems/maximum-profit-from-trading-stocks-with-discounts)
Canonical: https://scaleengineer.com/dsa/problems/maximum-profit-from-trading-stocks-with-discounts
**Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming)
**Algorithms:** [Depth-First Search](https://scaleengineer.com/algorithms/depth-first-search)
**Data structures:** Array, Tree
---
## Problem
You are given an integer `n`, representing the number of employees in a company. Each employee is assigned a unique ID from 1 to `n`, and employee 1 is the CEO. You are given two **1-based** integer arrays, `present` and `future`, each of length `n`, where:

* `present[i]` represents the **current** price at which the `ith` employee can buy a stock today.
* `future[i]` represents the **expected** price at which the `ith` employee can sell the stock tomorrow.

The company's hierarchy is represented by a 2D integer array `hierarchy`, where `hierarchy[i] = [ui, vi]` means that employee `ui` is the direct boss of employee `vi`.

Additionally, you have an integer `budget` representing the total funds available for investment.

However, the company has a discount policy: if an employee's direct boss purchases their own stock, then the employee can buy their stock at **half** the original price (`floor(present[v] / 2)`).

Return the **maximum** profit that can be achieved without exceeding the given budget.

**Note:**

* You may buy each stock at most **once**.
* You **cannot** use any profit earned from future stock prices to fund additional investments and must buy only from `budget`.

**Example 1:**

**Input:** n = 2, present = \[1,2\], future = \[4,3\], hierarchy = \[\[1,2\]\], budget = 3

**Output:** 5

**Explanation:**

![](https://assets.glich.co/dsa/maximum-profit-from-trading-stocks-with-discounts/image0.png)

* Employee 1 buys the stock at price 1 and earns a profit of `4 - 1 = 3`.
* Since Employee 1 is the direct boss of Employee 2, Employee 2 gets a discounted price of `floor(2 / 2) = 1`.
* Employee 2 buys the stock at price 1 and earns a profit of `3 - 1 = 2`.
* The total buying cost is `1 + 1 = 2 <= budget`. Thus, the maximum total profit achieved is `3 + 2 = 5`.

**Example 2:**

**Input:** n = 2, present = \[3,4\], future = \[5,8\], hierarchy = \[\[1,2\]\], budget = 4

**Output:** 4

**Explanation:**

![](https://assets.glich.co/dsa/maximum-profit-from-trading-stocks-with-discounts/image1.png)

* Employee 2 buys the stock at price 4 and earns a profit of `8 - 4 = 4`.
* Since both employees cannot buy together, the maximum profit is 4.

**Example 3:**

**Input:** n = 3, present = \[4,6,8\], future = \[7,9,11\], hierarchy = \[\[1,2\],\[1,3\]\], budget = 10

**Output:** 10

**Explanation:**

![](https://assets.glich.co/dsa/maximum-profit-from-trading-stocks-with-discounts/image2.png)

* Employee 1 buys the stock at price 4 and earns a profit of `7 - 4 = 3`.
* Employee 3 would get a discounted price of `floor(8 / 2) = 4` and earns a profit of `11 - 4 = 7`.
* Employee 1 and Employee 3 buy their stocks at a total cost of `4 + 4 = 8 <= budget`. Thus, the maximum total profit achieved is `3 + 7 = 10`.

**Example 4:**

**Input:** n = 3, present = \[5,2,3\], future = \[8,5,6\], hierarchy = \[\[1,2\],\[2,3\]\], budget = 7

**Output:** 12

**Explanation:**

![](https://assets.glich.co/dsa/maximum-profit-from-trading-stocks-with-discounts/image3.png)

* Employee 1 buys the stock at price 5 and earns a profit of `8 - 5 = 3`.
* Employee 2 would get a discounted price of `floor(2 / 2) = 1` and earns a profit of `5 - 1 = 4`.
* Employee 3 would get a discounted price of `floor(3 / 2) = 1` and earns a profit of `6 - 1 = 5`.
* The total cost becomes `5 + 1 + 1 = 7 <= budget`. Thus, the maximum total profit achieved is `3 + 4 + 5 = 12`.

**Constraints:**

* `1 <= n <= 160`
* `present.length, future.length == n`
* `1 <= present[i], future[i] <= 50`
* `hierarchy.length == n - 1`
* `hierarchy[i] == [ui, vi]`
* `1 <= ui, vi <= n`
* `ui != vi`
* `1 <= budget <= 160`
* There are no duplicate edges.
* Employee 1 is the direct or indirect boss of every employee.
* The input graph `hierarchy `is **guaranteed** to have no cycles.

# Approaches
## Brute Force
This approach explores every possible combination of buying or not buying a stock for each employee. It iterates through all `2^n` subsets of employees. For each subset, it calculates the total cost, considering the discount rule, and the total profit. It then keeps track of the maximum profit found among all combinations that do not exceed the given budget.
**Time:** O(2^n * n). There are `2^n` subsets to check. For each subset, we may iterate through all `n` employees to calculate the total cost and profit, considering the parent-child discount dependencies. · **Space:** O(n) to store the parent map for quick lookups.
**Pros:** Simple to conceptualize and implement.; Guaranteed to find the correct answer for small inputs.
**Cons:** Extremely inefficient due to its exponential time complexity.; Infeasible for the given constraints of `n` up to 160.
### Explanation
The brute-force method systematically checks every single possibility. Since for each of the `n` employees we have two choices (either buy their stock or not), there are `2^n` total combinations of purchases. We can represent each combination as a subset of employees for whom we buy stocks.

The algorithm iterates through each of these `2^n` subsets. For every subset, it calculates the total cost of buying the stocks. This calculation must account for the discount rule: if an employee's boss is also in the subset, the employee gets a 50% discount. After computing the total cost and total profit for the subset, it checks if the cost is within the `budget`. If it is, the profit is compared with the maximum profit found so far, and the maximum is updated if necessary. While simple, this approach is computationally expensive and only practical for very small values of `n`.
### Algorithm
- Build a parent map from the `hierarchy` data to easily check an employee's boss.
- Initialize `max_profit = 0`.
- Iterate through all `2^n` possible subsets of employees. A number `i` from `0` to `2^n - 1` can represent a subset, where the `j`-th bit being set means employee `j+1` is in the subset.
- For each subset:
  - Initialize `current_cost = 0` and `current_profit = 0`.
  - For each employee `j` from `1` to `n`:
    - If employee `j` is in the current subset:
      - Determine the purchase price. Check if `j`'s parent exists and is also in the subset.
      - If the parent is also in the subset, the price is `floor(present[j-1] / 2)`.
      - Otherwise, the price is `present[j-1]`.
      - Add the price to `current_cost`.
      - Add `future[j-1] - price` to `current_profit`.
  - If `current_cost <= budget`, update `max_profit = max(max_profit, current_profit)`.
- Return `max_profit`.

## Tree Dynamic Programming with Knapsack
This efficient approach models the problem as a tree knapsack problem. It uses dynamic programming combined with a post-order traversal (DFS) on the employee hierarchy tree. For each employee (node), it computes the maximum profit achievable for their entire subtree for every possible budget allocation. Crucially, to handle the discount dependency, it maintains two separate DP results for each subtree: one for the case where the employee's parent buys their stock, and one for the case where they don't.
**Time:** O(N * budget^2). The `dfs` function is called once for each of the `N` nodes. Inside `dfs(u)`, the dominant operation is merging the children's DP tables. If a node `u` has `d` children, this takes `O(d * budget^2)`. Since the sum of degrees in a tree is `2*(N-1)`, the total time complexity is `O(N * budget^2)`. · **Space:** O(N * budget). The recursion depth can be up to `N`, and at each level, we store DP tables. With memoization, we store the results for each node, leading to `N` pairs of DP tables, each of size `budget + 1`.
**Pros:** Highly efficient and solves the problem within the given constraints.; Correctly models and solves the complex dependencies in the problem.
**Cons:** More complex to understand and implement correctly.; The state space and transitions require careful handling to avoid bugs.
### Explanation
This approach leverages the tree structure of the employee hierarchy to build a solution from the bottom up. A recursive function `dfs(u)` is defined to solve the problem for the subtree rooted at employee `u`.

The key idea is that the decision to buy a stock for an employee `u` affects the cost for their direct subordinates. Therefore, the optimal solution for `u`'s subtree depends on whether `u`'s parent buys a stock. To capture this, `dfs(u)` returns two arrays, each representing a DP table of size `budget + 1`. One table stores the maximum profits for `u`'s subtree assuming `u`'s parent buys their stock (so `u` gets a discount), and the other assumes the parent does not.

In the post-order traversal, for any node `u`, we first recursively solve for all its children. Then, we combine the results from the children's subtrees using a knapsack-like merging algorithm. This gives us the total possible profit from all children subtrees for any given budget, considering whether `u` buys its stock or not. Finally, we incorporate the two choices for `u` itself (buy or not buy) to compute the two final DP tables for `u` to be passed up to its parent.

```java
class Solution {
    List<Integer>[] adj;
    int[] present;
    int[] future;
    int budget;
    int[][][] memo;

    public int maximumProfit(int n, int[] present, int[] future, int[][] hierarchy, int budget) {
        this.adj = new ArrayList[n];
        for (int i = 0; i < n; i++) {
            adj[i] = new ArrayList<>();
        }
        for (int[] edge : hierarchy) {
            adj[edge[0] - 1].add(edge[1] - 1);
        }
        this.present = present;
        this.future = future;
        this.budget = budget;
        this.memo = new int[n][][];

        int[][] resultDps = dfs(0);
        return resultDps[0][budget];
    }

    private int[][] dfs(int u) {
        if (memo[u] != null) {
            return memo[u];
        }

        int[] dpIfUBuys = new int[budget + 1];
        int[] dpIfUDoesnt = new int[budget + 1];

        for (int v : adj[u]) {
            int[][] childDps = dfs(v);
            int[] dpVParentBuys = childDps[1];
            int[] dpVParentDoesnt = childDps[0];

            int[] nextDpIfUBuys = new int[budget + 1];
            int[] nextDpIfUDoesnt = new int[budget + 1];

            for (int b = 0; b <= budget; b++) {
                for (int bChild = 0; bChild <= b; bChild++) {
                    nextDpIfUBuys[b] = Math.max(nextDpIfUBuys[b], dpIfUBuys[b - bChild] + dpVParentBuys[bChild]);
                    nextDpIfUDoesnt[b] = Math.max(nextDpIfUDoesnt[b], dpIfUDoesnt[b - bChild] + dpVParentDoesnt[bChild]);
                }
            }
            dpIfUBuys = nextDpIfUBuys;
            dpIfUDoesnt = nextDpIfUDoesnt;
        }

        int[][] result = new int[2][budget + 1];
        
        int costFull = present[u];
        int profitFull = future[u] - costFull;
        for (int b = 0; b <= budget; b++) {
            int profitDontBuy = dpIfUDoesnt[b];
            int profitBuy = (b >= costFull) ? profitFull + dpIfUBuys[b - costFull] : -1;
            result[0][b] = Math.max(profitDontBuy, profitBuy);
        }

        int costDisc = present[u] / 2;
        int profitDisc = future[u] - costDisc;
        for (int b = 0; b <= budget; b++) {
            int profitDontBuy = dpIfUDoesnt[b];
            int profitBuy = (b >= costDisc) ? profitDisc + dpIfUBuys[b - costDisc] : -1;
            result[1][b] = Math.max(profitDontBuy, profitBuy);
        }
        
        for (int i = 0; i < 2; i++) {
            for (int b = 1; b <= budget; b++) {
                result[i][b] = Math.max(result[i][b], result[i][b - 1]);
            }
        }

        return memo[u] = result;
    }
}
```
### Algorithm
- First, build an adjacency list to represent the employee hierarchy as a tree, with the CEO (employee 1) as the root.
- Define a recursive DFS function, let's say `dfs(u)`, that performs a post-order traversal starting from node `u`.
- This function computes and returns two DP tables (arrays of size `budget + 1`): 
  - `dp_table_1`: Max profit for `u`'s subtree assuming `u`'s parent **does not** buy their stock.
  - `dp_table_2`: Max profit for `u`'s subtree assuming `u`'s parent **does** buy their stock.
- **Base Case (Leaf Node `u`):** The DP tables are populated based on two choices: not buying `u`'s stock (profit 0) or buying it (at full or discounted price depending on which table is being computed).
- **Recursive Step (Internal Node `u`):**
  1. Recursively call `dfs` for all children of `u` to get their DP tables.
  2. Combine the children's results. This involves a knapsack-style merge. We create two aggregate DP tables for the children: one by merging their `dp_table_1`s (for when `u` doesn't buy) and another by merging their `dp_table_2`s (for when `u` buys). Each merge operation takes `O(budget^2)`.
  3. With the combined children's profits, compute the final DP tables for `u`. For each budget `b`, consider two main options:
     a. **Don't buy `u`'s stock:** Profit comes from the combined children's subtrees.
     b. **Buy `u`'s stock:** Profit is `profit_of_u` plus the combined profit from children's subtrees (using the appropriate merged table). The cost and profit for `u` depend on whether its own parent buys stock.
  4. For each budget `b`, take the maximum profit from the available options.
  5. After filling the tables, propagate the maximums (`table[b] = max(table[b], table[b-1])`) to ensure `table[b]` holds the max profit for a budget *at most* `b`.
- The final answer is obtained by calling `dfs(0)` (for the CEO) and taking the value at `result[0][budget]`, as the CEO has no parent.