3562. Maximum Profit from Trading Stocks with Discounts LeetCode Solution

Last updated: July 31, 2025

In this guide, you will get 3562. Maximum Profit from Trading Stocks with Discounts LeetCode Solution with the best time and space complexity. The solution to Maximum Profit from Trading Stocks with Discounts problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Maximum Profit from Trading Stocks with Discounts solution in C++
Maximum Profit from Trading Stocks with Discounts solution in Java
Maximum Profit from Trading Stocks with Discounts solution in Python
Additional Resources

3562. Maximum Profit from Trading Stocks with Discounts LeetCode Solution image

Problem Statement of Maximum Profit from Trading Stocks with Discounts

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 ith employee can buy a stock today.
future[i] represents the expected price at which the ith employee can sell the stock tomorrow.

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:

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] == [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.

Complexity Analysis

Time Complexity:
Space Complexity:

3562. Maximum Profit from Trading Stocks with Discounts LeetCode Solution in C++

class Solution:
  def maxProfit(
      self,
      n: int,
      present: list[int],
      future: list[int],
      hierarchy: list[list[int]],
      budget: int,
  ) -> int:
    tree = [[] for _ in range(n)]

    for u, v in hierarchy:
      tree[u - 1].append(v - 1)

    @functools.lru_cache(None)
    def dp(u: int, parent: int) -> tuple[list[int], list[int]]:
      noDiscount = [0] * (budget + 1)
      withDiscount = [0] * (budget + 1)

      for v in tree[u]:
        if v == parent:
          continue
        childNoDiscount, childWithDiscount = dp(v, u)
        noDiscount = self._merge(noDiscount, childNoDiscount)
        withDiscount = self._merge(withDiscount, childWithDiscount)

      newDp0 = noDiscount[:]
      newDp1 = noDiscount[:]

      # 1. Buy current node at full cost (no discount)
      fullCost = present[u]
      for b in range(fullCost, budget + 1):
        profit = future[u] - fullCost
        newDp0[b] = max(newDp0[b], withDiscount[b - fullCost] + profit)

      # 2. Buy current node at half cost (discounted by parent)
      halfCost = present[u] // 2
      for b in range(halfCost, budget + 1):
        profit = future[u] - halfCost
        newDp1[b] = max(newDp1[b], withDiscount[b - halfCost] + profit)

      return newDp0, newDp1

    return max(dp(0, -1)[0])

  def _merge(self, dpA: list[int], dpB: list[int]) -> list[int]:
    merged = [-math.inf] * len(dpA)
    for i, a in enumerate(dpA):
      for j in range(len(dpA) - i):
        merged[i + j] = max(merged[i + j], a + dpB[j])
    return merged
/* code provided by PROGIEZ */

3562. Maximum Profit from Trading Stocks with Discounts LeetCode Solution in Java

N/A
// code provided by PROGIEZ

3562. Maximum Profit from Trading Stocks with Discounts LeetCode Solution in Python

N/A
 # code by PROGIEZ

Additional Resources

Happy Coding! Keep following PROGIEZ for more updates and solutions.

Table of Contents