Skip to main content
Talentd

Maximum Profit from Trading Stocks with Discounts - Solution & Explanation

HardArrayDynamic ProgrammingTreeDepth-First Search18 min readAsked at: Meta, Google
Practice this problem

Problem Statement

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:

  • 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:

  • 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:

  • 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:

  • 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:

  • 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.

Approach Overview

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.

Solution

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:

  1. Whether node 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.
  2. How to allocate the budget among node 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.

  • If j \lt cost, then u cannot purchase stocks, in which case f[j][pre] = nxt[j][0].
  • If j geq cost, 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)$.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force Subset EnumerationO(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 ProgrammingO(n)O(n)Preferred implementation for clean DFS aggregation and interview solutions

Video Solution

Maximum Profit from Trading Stocks with Discounts | Super Detailed | Beginner | Leetcode 3562 | MIK • codestorywithMIK • 7,444 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Maximum Profit from Trading Stocks with Discounts easy or hard?
The problem is classified as Hard because it combines tree traversal with dynamic programming state transitions. Recognizing the two-state DP on a hierarchical structure is the key step that makes the solution efficient.
Maximum Profit from Trading Stocks with Discounts Python/Java solution
Most implementations use DFS-based tree DP. Each function call returns two values representing the profit when buying or skipping the stock. The same logic works across Python, Java, C++, Go, and TypeScript by storing child nodes in adjacency lists and combining results during recursion.
How to solve Maximum Profit from Trading Stocks with Discounts in O(n)?
Build the company hierarchy as an adjacency list and run DFS from the root. For every node compute two values: maximum profit when the employee buys and when they skip. While processing children, apply discounted cost if the parent bought the stock. Combining these states across the tree yields the final maximum profit in linear time.
What is the best approach for Maximum Profit from Trading Stocks with Discounts?
The optimal approach is Tree Dynamic Programming using Depth-First Search. Each employee node maintains two states: profit if they buy the stock and profit if they skip it. DFS aggregates results from children while applying discounts when the parent buys. This reduces the exponential decision space to O(n) time.
Is Maximum Profit from Trading Stocks with Discounts asked at Google/Amazon/Meta?
Tree dynamic programming problems with parent-child constraints are common in interviews at companies like Google, Amazon, and Meta. Variants appear in questions involving organizational hierarchies, dependency graphs, or resource allocation on trees.
What data structure is used in Maximum Profit from Trading Stocks with Discounts?
The core structure is a tree represented using an adjacency list built from arrays describing manager relationships. Depth-first search traverses the tree while dynamic programming stores two profit states per node.
What is the time complexity of Maximum Profit from Trading Stocks with Discounts?
The optimal Tree DP solution runs in O(n) time because each node and edge in the company hierarchy tree is processed once during DFS. Space complexity is O(n) due to recursion stack and dynamic programming state storage.

Ready to solve this problem?

Practice Maximum Profit from Trading Stocks with Discounts with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays