Maximum Profit from Trading Stocks with Discounts

Maximum Profit from Trading Stocks with Discounts - 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 who 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 i-th employee can buy a stock today
future[i] represents the expected price at which the i-th employee can sell the stock tomorrow

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

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

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.

Input & Output

Example 1 — Basic Hierarchy

$ Input: n = 3, present = [10,5,3], future = [15,8,7], hierarchy = [[1,2],[1,3]], budget = 15

› Output: 12

💡 Note: Buy CEO's stock (cost 10, profit 5) and Employee 3's stock (cost 1 with discount, profit 4). Total cost: 11, total profit: 5+4+3 = 12

Example 2 — Limited Budget

$ Input: n = 3, present = [20,10,5], future = [25,15,10], hierarchy = [[1,2],[1,3]], budget = 10

› Output: 5

💡 Note: Can only buy Employee 3's stock (cost 5, profit 5). CEO's stock is too expensive.

Example 3 — Maximum Discount

$ Input: n = 2, present = [8,6], future = [12,10], hierarchy = [[1,2]], budget = 10

› Output: 8

💡 Note: Buy both: CEO (cost 8, profit 4) and Employee 2 with discount (cost 3, profit 4). Total: 8 profit.

Constraints

1 ≤ n ≤ 1000
1 ≤ present[i], future[i] ≤ 10⁴
1 ≤ budget ≤ 10⁵
hierarchy.length = n - 1

Visualization

Tap to expand

Key Insight: Discount policy creates dependency between parent and child decisions

Understanding the Visualization

Company Hierarchy

Build tree from boss-subordinate relationships

Discount Policy

Boss purchase gives 50% discount to subordinates

Optimization

Find maximum profit within budget constraint

Key Takeaway

🎯 Key Insight: The discount policy creates interdependence between employee decisions in the hierarchy tree

Asked in

G Google 15 a Amazon 12 M Microsoft 8 f Meta 6

This problem combines tree traversal with dynamic programming and knapsack-like optimization. The key insight is that each employee's purchase decision affects their subordinates' costs through the discount policy. The optimal approach uses memoized tree DP to explore buy/don't-buy decisions while considering budget constraints and discount cascading. Time: O(n × budget), Space: O(n × budget).

Common Approaches

Approach	Time	Space	Notes
✓ Memoized Tree DP	O(n × budget)	O(n × budget)	Use tree structure with memoization to avoid recalculating subproblems
Brute Force - Try All Combinations	O(n × 2^n)	O(n)	Generate all possible combinations of stock purchases and find maximum profit

Memoized Tree DP — Algorithm Steps

Build tree from hierarchy relationships
For each node, calculate DP states: buy vs don't buy
Use memoization to cache results
Consider discount effect from parent decisions

Visualization

Tap to expand

Step-by-Step Walkthrough

Build Tree

Create hierarchy tree from boss-subordinate relationships

DP with Cache

For each node, cache results for different budget/parent states

Optimal Choice

Choose buy vs don't buy to maximize profit

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX_N 1000
#define MAX_BUDGET 10000

int memo[MAX_N + 1][MAX_BUDGET + 1][2];
int memoSet[MAX_N + 1][MAX_BUDGET + 1][2];
int children[MAX_N + 1][MAX_N];
int childCount[MAX_N + 1];
int present[MAX_N], future[MAX_N];

int dfs(int node, int remainingBudget, int parentBought) {
    if (node == 0 || remainingBudget < 0) {
        return 0;
    }
    
    if (memoSet[node][remainingBudget][parentBought]) {
        return memo[node][remainingBudget][parentBought];
    }
    
    // Option 1: Don't buy this employee's stock
    int maxProfit = 0;
    for (int i = 0; i < childCount[node]; i++) {
        maxProfit += dfs(children[node][i], remainingBudget, 0);
    }
    
    // Option 2: Buy this employee's stock
    int cost = present[node - 1];
    if (parentBought) {
        cost = cost / 2;
    }
    
    if (remainingBudget >= cost) {
        int profitFromStock = future[node - 1] - present[node - 1];
        int childProfit = 0;
        for (int i = 0; i < childCount[node]; i++) {
            childProfit += dfs(children[node][i], remainingBudget - cost, 1);
        }
        
        int option2Profit = profitFromStock + childProfit;
        if (option2Profit > maxProfit) {
            maxProfit = option2Profit;
        }
    }
    
    memo[node][remainingBudget][parentBought] = maxProfit;
    memoSet[node][remainingBudget][parentBought] = 1;
    return maxProfit;
}

int solution(int n, int* presentArr, int* futureArr, int hierarchy[][2], int hierarchySize, int budget) {
    memset(memoSet, 0, sizeof(memoSet));
    memset(childCount, 0, sizeof(childCount));
    
    for (int i = 0; i < n; i++) {
        present[i] = presentArr[i];
        future[i] = futureArr[i];
    }
    
    for (int i = 0; i < hierarchySize; i++) {
        int boss = hierarchy[i][0];
        int subordinate = hierarchy[i][1];
        children[boss][childCount[boss]++] = subordinate;
    }
    
    return dfs(1, budget, 0);
}

int main() {
    int n = 3;
    int presentArr[] = {10, 5, 3};
    int futureArr[] = {15, 8, 7};
    int hierarchy[][2] = {{1, 2}, {1, 3}};
    int budget = 15;
    
    int result = solution(n, presentArr, futureArr, hierarchy, 2, budget);
    printf("%d\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n × budget)

Each employee has states up to budget amount, memoized

✓ Linear Growth

Space Complexity

O(n × budget)

Memoization table plus recursion stack depth

⚡ Linearithmic Space

22.3K Views

Medium Frequency

~35 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Memoized Tree DP — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler