Maximum Profit from Trading Stocks with Discounts
You receive 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 receive two 1-based integer arrays, present and future, each of length n, where:
-
present[i]represents the current price at which thei themployee can buy a stock today. -
future[i]represents the expected price at which thei themployee 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.
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)).
Produce 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: 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 is3 + 2 = 5.
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.
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) = 4and earns a profit of11 - 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 is3 + 7 = 10.
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) = 1and earns a profit of5 - 1 = 4. -
Employee 3 would get a discounted price of
floor(3 / 2) = 1and earns a profit of6 - 1 = 5. -
The total cost becomes
5 + 1 + 1 = 7 <= budget. Thus, the maximum total profit achieved is3 + 4 + 5 = 12.
Constraints
1 <= n <= 160present.length, future.length == n1 <= present[i], future[i] <= 50hierarchy.length == n - 1hierarchy[i] == [u i, v i ]1 <= u i, v i <= nu i != v i1 <= budget <= 160- There are no duplicate edges.
- Employee 1 is the direct or indirect boss of every employee.
- The input graph
hierarchyis guaranteed to have no cycles.
Did this problem appear in one of your interviews?
Responses stay private.