Leetcode Problem 2538. Difference Between Maximum and Minimum Price Sum

2538. Difference Between Maximum and Minimum Price Sum

Leetcode Solutions

Re rooting | O(N) clean code

  1. Initialize an adjacency list to represent the graph.
  2. Perform the first DFS to compute the maximum path sum for each node when it is the root.
  3. Store the maximum path sum in a 2D array dp where dp[i][0] represents the maximum path sum including node i and dp[i][1] represents the second maximum path sum.
  4. Perform the second DFS to update the dp array by considering re-rooting at each node.
  5. During the second DFS, update the maximum path sum for the children by considering the maximum path sum from the parent node.
  6. Keep track of the global maximum difference between the maximum and minimum path sums.
  7. Return the global maximum difference as the result.
UML Thumbnail

Java , simple DFS + MEMO

Ask Question

Programming Language
image/screenshot of info(optional)
Full Screen
Loading...

Suggested Answer

Answer
Full Screen
Copy Answer Code
Loading...