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, is the direct or indirect boss of every employee. 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:
budget.
Example 1:
Input: n = 2, present = [1,2], future = [4,3], hierarchy = [[1,2]], budget = 3
Output: 5
Explanation:
4 - 1 = 3.floor(2 / 2) = 1.3 - 1 = 2.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:
8 - 4 = 4.Example 3:
Input: n = 3, present = [4,6,8], future = [7,9,11], hierarchy = [[1,2],[1,3]], budget = 10
Output: 10
Explanation:
7 - 4 = 3.floor(8 / 2) = 4 and earns a profit of 11 - 4 = 7.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:
8 - 5 = 3.floor(2 / 2) = 1 and earns a profit of 5 - 1 = 4.floor(3 / 2) = 1 and earns a profit of 6 - 1 = 5.5 + 1 + 1 = 7 <= budget. Thus, the maximum total profit achieved is 3 + 4 + 5 = 12.
Constraints:
1 <= n <= 160present.length, future.length == n1 <= present[i], future[i] <= 50hierarchy.length == n - 1hierarchy[i] == [ui, vi]1 <= ui, vi <= nui != vi1 <= budget <= 160hierarchy is guaranteed to have no cycles.Problem Overview: You are given a company structure represented as a tree where each employee can buy a stock. Each stock has a cost and expected profit, and some employees receive a discount if their manager buys first. The goal is to choose which employees buy stocks so the total profit is maximized while respecting the dependency between managers and subordinates.
Approach 1: Brute Force Subset Exploration (Exponential Time)
The most direct way is to try every combination of employees who buy stocks. For each subset, verify whether discount rules apply and compute the resulting profit. This requires iterating through all possible buy/not-buy states and recalculating costs depending on whether a parent in the management tree purchased the stock. The approach quickly becomes infeasible because the number of states grows exponentially with the number of employees. Time complexity is O(2^n) and space complexity is O(n) for recursion.
Approach 2: DFS with Memoization (Top-Down Tree DP) (O(n))
The dependency only exists between a node and its parent, which means the company hierarchy forms a natural tree dynamic programming structure. Run a depth-first search from the root and maintain two states for every node: profit when the employee buys the stock and profit when they do not. If the parent buys, the child may purchase at a discounted cost; otherwise the normal cost applies. During DFS, aggregate results from all children and store computed states in a DP table to avoid recomputation.
The transition is straightforward. When an employee buys, calculate their profit using the correct price (discounted or full) and add the best outcome from each child depending on whether that child benefits from the discount. When they skip buying, children evaluate independently using the non-discount state. Because each node is processed once and each edge is traversed once, the algorithm runs in O(n) time with O(n) space for recursion and DP storage.
Approach 3: Bottom-Up Tree Dynamic Programming (O(n))
A bottom-up version computes the same states but aggregates results while returning from DFS calls. Each node returns a pair [notBuy, buy]. While combining child results, you accumulate the maximum profit contribution from each subtree depending on the parent decision. This avoids repeated state checks and keeps transitions localized to the recursion stack. The algorithm still runs in O(n) time and uses O(n) space for the adjacency list and recursion.
Recommended for interviews: Interviewers expect the tree DP formulation using DFS. Explaining the brute force first shows you understand the decision space. Transitioning to a two-state DP on a dynamic programming tree demonstrates the key optimization and reduces exponential exploration to linear time.
For each node u, we maintain a 2D array f_u[j][pre], representing the maximum profit that can be obtained in the subtree rooted at u with a budget not exceeding j and whether u's manager purchased stocks (where pre=1 means purchased, and pre=0 means not purchased). The answer is f_1[budget][0].
For node u, the function dfs(u) returns a (budget+1) times 2 2D array f, representing the maximum profit that can be obtained in the subtree rooted at u with a budget not exceeding j and whether u's manager purchased stocks.
For u, we need to consider two things:
u itself buys stocks (which will consume part of the budget cost, where cost = \lfloor present[u] / (pre + 1) \rfloor), and increase the profit by future[u] - cost.u's child nodes v to maximize profit. We treat each child node's dfs(v) as an "item" and use a knapsack approach to merge the subtree profits into the current u's nxt array.In the specific implementation, we first initialize a (budget+1) times 2 2D array nxt, representing the profits that have been merged from child nodes. Then for each child node v, we recursively call dfs(v) to get the profit array fv of the child node, and use a knapsack approach to merge fv into nxt.
The merge formula is:
$
nxt[j][pre] = max(nxt[j][pre], nxt[j - j_v][pre] + fv[j_v][pre])
where j_v represents the budget allocated to child node v.
After merging all child nodes, nxt[j][pre] represents the maximum profit that can be obtained by allocating the entire budget j to child nodes when u itself has not yet decided whether to buy stocks, and u's manager's purchase state is pre.
Finally, we decide whether u purchases stocks.
, then u cannot purchase stocks, in which case f[j][pre] = nxt[j][0]., then u can choose to purchase or not purchase stocks, in which case f[j][pre] = max(nxt[j][0], nxt[j - cost][1] + (future[u] - cost)).Finally, return f.
The answer is dfs(1)[budget][0].
The time complexity is O(n times budget^2), and the space complexity is O(n times budget)$.
Python
Java
C++
Go
TypeScript
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Subset Enumeration | O(2^n) | O(n) | Only for understanding the decision space or very small inputs |
| DFS with Memoization (Top-Down Tree DP) | O(n) | O(n) | General case when the company hierarchy forms a tree and parent decisions affect children |
| Bottom-Up Tree Dynamic Programming | O(n) | O(n) | Preferred implementation for clean DFS aggregation and interview solutions |
Maximum Profit from Trading Stocks with Discounts | Super Detailed | Beginner | Leetcode 3562 | MIK • codestorywithMIK • 7,046 views views
Watch 9 more video solutions →Practice Maximum Profit from Trading Stocks with Discounts with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor