Maximum Profit from Trading Stocks with Discounts
You are given an integer n, representing the number of employees in a company.
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. You are given two 1-based integer arrays, present and future, each of length n, where:
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:
Example 1
Input: n = 2, present = [1,2], future = [4,3], hierarchy = [[1,2]], budget = 3
Output: 5
Example 2
Input: n = 2, present = [3,4], future = [5,8], hierarchy = [[1,2]], budget = 4
Output: 4
Example 3
Input: n = 3, present = [4,6,8], future = [7,9,11], hierarchy = [[1,2],[1,3]], budget = 10
Output: 10
Example 4
Input: n = 3, present = [5,2,3], future = [8,5,6], hierarchy = [[1,2],[2,3]], budget = 7
Output: 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.
Hints
Companies
No companies reported yet.
Discussion
Sign in to join the discussion.
Loading discussion...
Test results
No test cases yet.