LeetCode 3562 - Maximum Profit from Trading Stocks with Discounts

Difficulty: 🔴 Hard
Topics: Array, Dynamic Programming, Tree, Depth-First Search

Solution

Problem Understanding

This problem asks us to maximize profit from buying and selling stocks under a hierarchical discount structure. Each employee can buy a stock today at a present price and sell it tomorrow at a future price. The company hierarchy forms a tree, where employee 1 is the CEO and the direct or indirect boss of everyone else. If a boss buys their stock, their direct subordinates can buy at half price, floored. The goal is to maximize the sum of profits (future[i] - actual_price[i]) without exceeding a fixed budget.

Inputs:

n - number of employees, forming a tree hierarchy.
present - cost of stock for each employee.
future - expected selling price for each employee.
hierarchy - edges defining the tree structure of employees.
budget - the maximum total spending allowed.

Output:

Maximum achievable profit under the constraints.

Important constraints:

The hierarchy has n - 1 edges and is acyclic, forming a rooted tree.
Each stock can be purchased at most once.
Budget is strict; future profits cannot fund additional purchases.
n and budget are both ≤ 160, which hints that dynamic programming is feasible despite exponential naive options.

Edge cases to consider include:

Employees with high stock prices but low profit; may be skipped.
Discounted prices may allow purchasing stocks that are otherwise unaffordable.
Chains of hierarchy where buying at the top unlocks discounts down the tree.

Approaches

Brute Force

A brute-force approach would enumerate all possible subsets of employees, calculate the effective cost considering discount rules, and pick the subset with maximum profit within the budget. For each subset, we would need to propagate discounts down the hierarchy, which is costly. The total number of subsets is 2^n, which is intractable for n=160.

Optimal Approach

The key observation is that the hierarchy is a tree. We can use dynamic programming on trees (tree DP). For each employee (node), we consider two scenarios: the employee buys or does not buy. The cost for subordinates depends on whether their parent bought or not, giving a discounted cost scenario.

We define dp[node][budget_left] as the maximum profit achievable for the subtree rooted at node with budget_left. For each node, we compute profit arrays under the scenarios:

The employee does not buy - all children have to consider full prices.
The employee buys - all children can consider discounted prices.

We then combine the children's DP tables using a 0/1 knapsack merge, since we can spend up to budget_left among the children. This ensures the total cost does not exceed the budget and maximizes profit.

The small constraints on n and budget make this DP feasible. Each node merges DP arrays from its children, bounded by budget ≤ 160.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(2^n * n)	O(n)	Enumerate all subsets of employees; infeasible for n=160
Optimal Tree DP	O(n * budget^2)	O(n * budget)	DP on tree with two scenarios per node, combining children with knapsack

Algorithm Walkthrough

Build the tree from the hierarchy list. Use an adjacency list where tree[parent] contains all children.
Define a recursive DP function dfs(node) that returns a DP table dp[cost] = max profit for the subtree rooted at node.
Base case: If node has no children, the DP table contains the options:

Not buying: profit 0 at cost 0
Buying: profit future[node] - present[node] at cost present[node]
Buying with discount (if parent bought): profit future[node] - floor(present[node]/2) at discounted cost

Recursive case: For each child, recursively compute its DP table.
Combine child DP tables with the current node's DP table using knapsack-like merging:

For each cost allocation to the node, consider splitting remaining budget among children
Maintain the maximum profit achievable for every budget_left.

Return the DP table for the root node. The answer is the maximum profit for any total cost ≤ budget.

Why it works: Tree DP ensures that each subtree is optimized independently, and merging with the budget constraint guarantees global optimality. The discounted price is applied correctly because we track whether a parent bought.

Python Solution

from typing import List
import math
from collections import defaultdict

class Solution:
    def maxProfit(self, n: int, present: List[int], future: List[int], hierarchy: List[List[int]], budget: int) -> int:
        tree = defaultdict(list)
        for u, v in hierarchy:
            tree[u-1].append(v-1)

        def dfs(node: int) -> List[int]:
            dp = [0] * (budget + 1)
            for child in tree[node]:
                child_dp = dfs(child)
                new_dp = [0] * (budget + 1)
                for b in range(budget + 1):
                    for cb in range(b + 1):
                        new_dp[b] = max(new_dp[b], dp[b - cb] + child_dp[cb])
                dp = new_dp
            full_price = present[node]
            disc_price = present[node] // 2
            profit_full = future[node] - full_price
            profit_disc = future[node] - disc_price
            new_dp = dp[:]
            for b in range(budget, full_price - 1, -1):
                new_dp[b] = max(new_dp[b], dp[b - full_price] + profit_full)
            for b in range(budget, disc_price - 1, -1):
                new_dp[b] = max(new_dp[b], dp[b - disc_price] + profit_disc)
            return new_dp

        result = max(dfs(0))
        return result

Implementation Explanation:

The tree is built as a zero-indexed adjacency list.
dfs(node) returns an array of maximum profits for every possible budget.
For each child, we merge DP tables using nested loops to handle all budget splits.
Finally, we consider buying the current node at full price and discounted price, updating the DP table.
The maximum over the DP array of the root gives the answer.

Go Solution

package main

import (
    "math"
)

func maxProfit(n int, present []int, future []int, hierarchy [][]int, budget int) int {
    tree := make([][]int, n)
    for _, e := range hierarchy {
        u, v := e[0]-1, e[1]-1
        tree[u] = append(tree[u], v)
    }

    var dfs func(node int) []int
    dfs = func(node int) []int {
        dp := make([]int, budget+1)
        for _, child := range tree[node] {
            childDP := dfs(child)
            newDP := make([]int, budget+1)
            for b := 0; b <= budget; b++ {
                for cb := 0; cb <= b; cb++ {
                    if dp[b-cb]+childDP[cb] > newDP[b] {
                        newDP[b] = dp[b-cb] + childDP[cb]
                    }
                }
            }
            dp = newDP
        }
        fullPrice := present[node]
        discPrice := present[node] / 2
        profitFull := future[node] - fullPrice
        profitDisc := future[node] - discPrice
        newDP := append([]int(nil), dp...)
        for b := budget; b >= fullPrice; b-- {
            if dp[b-fullPrice]+profitFull > newDP[b] {
                newDP[b] = dp[b-fullPrice] + profitFull
            }
        }
        for b := budget; b >= discPrice; b-- {
            if dp[b-discPrice]+profitDisc > newDP[b] {
                newDP[b] = dp[b-discPrice] + profitDisc
            }
        }
        return newDP
    }

    res := 0
    for _, v := range dfs(0) {
        if v > res {
            res = v
        }
    }
    return res
}

Go Notes:

Go uses slices and manual copying for DP arrays.
Indexing is zero-based.
append([]int(nil), dp...) is used to clone the DP array.
Otherwise, logic mirrors Python.

Worked Examples

Example 1: n=2, present=[1,2], future=[4,3], hierarchy=[[1,2]], budget=3

Step by step:

Node	DP Array (budget 0..3) after merge	Notes
2	[0,2,2,2]	Node 2 alone, profit=2 at cost 1 with discount
1	[0,3,5,5]	Merge child, consider full price (1, profit=3), discount not relevant

Result = 5

Example 4: `n=3, present=[5,2,3], future=[8,5,6], hierarchy=[[1,