3562. Maximum Profit from Trading Stocks with Discounts
Hard
50 Points
Array
Dynamic Programming
Tree
Depth-First Search
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:
Examples
Example 1
Input: n = 2, present = [1,2], future = [4,3], hierarchy = [[1,2]], budget = 3
Output: 5
Explanation:
Example 2
Input: n = 2, present = [3,4], future = [5,8], hierarchy = [[1,2]], budget = 4
Output: 4
Explanation:
Example 3
Input: n = 3, present = [4,6,8], future = [7,9,11], hierarchy = [[1,2],[1,3]], budget = 10
Output: 10
Explanation:
Example 4
Input: n = 3, present = [5,2,3], future = [8,5,6], hierarchy = [[1,2],[2,3]], budget = 7
Output: 12
Explanation:
Constraints
1 <= n <= 160present.length, future.length == n1 <= present[i], future[i] <= 50hierarchy.length == n - 1hierarchy[i] == [ui, vi]1 <= ui, vi <= nui != vi1 <= budget <= 160There 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.
3562. Maximum Profit from Trading Stocks with Discounts
Hard
50 Points
Array
Dynamic Programming
Tree
Depth-First Search
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:
Examples
Example 1
Input: n = 2, present = [1,2], future = [4,3], hierarchy = [[1,2]], budget = 3
Output: 5
Explanation:
Example 2
Input: n = 2, present = [3,4], future = [5,8], hierarchy = [[1,2]], budget = 4
Output: 4
Explanation:
Example 3
Input: n = 3, present = [4,6,8], future = [7,9,11], hierarchy = [[1,2],[1,3]], budget = 10
Output: 10
Explanation:
Example 4
Input: n = 3, present = [5,2,3], future = [8,5,6], hierarchy = [[1,2],[2,3]], budget = 7
Output: 12
Explanation:
Constraints
1 <= n <= 160present.length, future.length == n1 <= present[i], future[i] <= 50hierarchy.length == n - 1hierarchy[i] == [ui, vi]1 <= ui, vi <= nui != vi1 <= budget <= 160There 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.