Maximum Profit from Trading Stocks with Discounts - Video Solutions

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.