3562. Maximum Profit from Trading Stocks with Discounts

Description

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:

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.

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:

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.

Example 1:

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 is 3 + 2 = 5.

Example 2:

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.

Example 3:

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) = 4 and earns a profit of 11 - 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 is 3 + 7 = 10.

Example 4:

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) = 1 and earns a profit of 5 - 1 = 4.
Employee 3 would get a discounted price of floor(3 / 2) = 1 and earns a profit of 6 - 1 = 5.
The total cost becomes 5 + 1 + 1 = 7 <= budget. Thus, the maximum total profit achieved is 3 + 4 + 5 = 12.

Constraints:

1 <= n <= 160
present.length, future.length == n
1 <= present[i], future[i] <= 50
hierarchy.length == n - 1
hierarchy[i] == [u_i, v_i]
1 <= u_i, v_i <= n
u_i != v_i
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.

Solutions

Solution 1

class Solution {
    private List<Integer>[] g;
    private int[] present;
    private int[] future;
    private int budget;

    public int maxProfit(int n, int[] present, int[] future, int[][] hierarchy, int budget) {
        this.present = present;
        this.future = future;
        this.budget = budget;

        g = new ArrayList[n + 1];
        Arrays.setAll(g, k -> new ArrayList<>());

        for (int[] e : hierarchy) {
            g[e[0]].add(e[1]);
        }

        return dfs(1)[budget][0];
    }

    private int[][] dfs(int u) {
        int[][] nxt = new int[budget + 1][2];

        for (int v : g[u]) {
            int[][] fv = dfs(v);
            for (int j = budget; j >= 0; j--) {
                for (int jv = 0; jv <= j; jv++) {
                    for (int pre = 0; pre < 2; pre++) {
                        int val = nxt[j - jv][pre] + fv[jv][pre];
                        if (val > nxt[j][pre]) {
                            nxt[j][pre] = val;
                        }
                    }
                }
            }
        }

        int[][] f = new int[budget + 1][2];
        int price = future[u - 1];

        for (int j = 0; j <= budget; j++) {
            for (int pre = 0; pre < 2; pre++) {
                int cost = present[u - 1] / (pre + 1);
                if (j >= cost) {
                    f[j][pre] = Math.max(nxt[j][0], nxt[j - cost][1] + (price - cost));
                } else {
                    f[j][pre] = nxt[j][0];
                }
            }
        }

        return f;
    }
}

class Solution {
public:
    int maxProfit(int n, vector<int>& present, vector<int>& future, vector<vector<int>>& hierarchy, int budget) {
        vector<vector<int>> g(n + 1);
        for (auto& e : hierarchy) {
            g[e[0]].push_back(e[1]);
        }

        auto dfs = [&](const auto& dfs, int u) -> vector<array<int, 2>> {
            vector<array<int, 2>> nxt(budget + 1);
            for (int j = 0; j <= budget; j++) nxt[j] = {0, 0};

            for (int v : g[u]) {
                auto fv = dfs(dfs, v);
                for (int j = budget; j >= 0; j--) {
                    for (int jv = 0; jv <= j; jv++) {
                        for (int pre = 0; pre < 2; pre++) {
                            int val = nxt[j - jv][pre] + fv[jv][pre];
                            if (val > nxt[j][pre]) {
                                nxt[j][pre] = val;
                            }
                        }
                    }
                }
            }

            vector<array<int, 2>> f(budget + 1);
            int price = future[u - 1];

            for (int j = 0; j <= budget; j++) {
                for (int pre = 0; pre < 2; pre++) {
                    int cost = present[u - 1] / (pre + 1);
                    if (j >= cost) {
                        f[j][pre] = max(nxt[j][0], nxt[j - cost][1] + (price - cost));
                    } else {
                        f[j][pre] = nxt[j][0];
                    }
                }
            }

            return f;
        };

        return dfs(dfs, 1)[budget][0];
    }
};

class Solution:
    def maxProfit(
        self,
        n: int,
        present: List[int],
        future: List[int],
        hierarchy: List[List[int]],
        budget: int,
    ) -> int:
        max = lambda a, b: a if a > b else b
        g = [[] for _ in range(n + 1)]
        for u, v in hierarchy:
            g[u].append(v)

        def dfs(u: int):
            nxt = [[0, 0] for _ in range(budget + 1)]
            for v in g[u]:
                fv = dfs(v)
                for j in range(budget, -1, -1):
                    for jv in range(j + 1):
                        for pre in (0, 1):
                            val = nxt[j - jv][pre] + fv[jv][pre]
                            if val > nxt[j][pre]:
                                nxt[j][pre] = val

            f = [[0, 0] for _ in range(budget + 1)]
            price = future[u - 1]

            for j in range(budget + 1):
                for pre in (0, 1):
                    cost = present[u - 1] // (pre + 1)
                    if j >= cost:
                        f[j][pre] = max(nxt[j][0], nxt[j - cost][1] + (price - cost))
                    else:
                        f[j][pre] = nxt[j][0]

            return f

        return dfs(1)[budget][0]

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

	var dfs func(u int) [][2]int
	dfs = func(u int) [][2]int {
		nxt := make([][2]int, budget+1)

		for _, v := range g[u] {
			fv := dfs(v)
			for j := budget; j >= 0; j-- {
				for jv := 0; jv <= j; jv++ {
					for pre := 0; pre < 2; pre++ {
						nxt[j][pre] = max(nxt[j][pre], nxt[j-jv][pre]+fv[jv][pre])
					}
				}
			}
		}

		f := make([][2]int, budget+1)
		price := future[u-1]

		for j := 0; j <= budget; j++ {
			for pre := 0; pre < 2; pre++ {
				cost := present[u-1] / (pre + 1)
				if j >= cost {
					buyProfit := nxt[j-cost][1] + (price - cost)
					f[j][pre] = max(nxt[j][0], buyProfit)
				} else {
					f[j][pre] = nxt[j][0]
				}
			}
		}
		return f
	}

	return dfs(1)[budget][0]
}

function maxProfit(
    n: number,
    present: number[],
    future: number[],
    hierarchy: number[][],
    budget: number,
): number {
    const g: number[][] = Array.from({ length: n + 1 }, () => []);

    for (const [u, v] of hierarchy) {
        g[u].push(v);
    }

    const dfs = (u: number): number[][] => {
        const nxt: number[][] = Array.from({ length: budget + 1 }, () => [0, 0]);

        for (const v of g[u]) {
            const fv = dfs(v);
            for (let j = budget; j >= 0; j--) {
                for (let jv = 0; jv <= j; jv++) {
                    for (let pre = 0; pre < 2; pre++) {
                        nxt[j][pre] = Math.max(nxt[j][pre], nxt[j - jv][pre] + fv[jv][pre]);
                    }
                }
            }
        }

        const f: number[][] = Array.from({ length: budget + 1 }, () => [0, 0]);
        const price = future[u - 1];

        for (let j = 0; j <= budget; j++) {
            for (let pre = 0; pre < 2; pre++) {
                const cost = Math.floor(present[u - 1] / (pre + 1));
                if (j >= cost) {
                    const profitIfBuy = nxt[j - cost][1] + (price - cost);
                    f[j][pre] = Math.max(nxt[j][0], profitIfBuy);
                } else {
                    f[j][pre] = nxt[j][0];
                }
            }
        }

        return f;
    };

    return dfs(1)[budget][0];
}

3562 - Maximum Profit from Trading Stocks with Discounts

3562. Maximum Profit from Trading Stocks with Discounts

Description

Solutions

Solution 1

All Problems

All Solutions

Welcome to Subscribe On Youtube

3562. Maximum Profit from Trading Stocks with Discounts

Description

Solutions

Solution 1

All Problems

All Solutions