Maximum Path Sum (Tree DP)
Learn Maximum Path Sum (Tree DP) (Dynamic Programming, Advanced DSA) with worked examples, diagrams and interview questions. Free on JavaSchoolLab.
Maximum Sum Path Between ANY Two Nodes Unlike a root-to-leaf path, this path can START and END anywhere, possibly "bending" at some peak node. Each node returns the best DOWNWARD-only extension it can offer its parent (since a parent can only chain ONE side, not both), while separately tracking the GLOBAL best full path (which CAN use both children at a peak).
More lessons in Dynamic Programming
- Fibonacci (DP)
- Climbing Stairs
- House Robber
- Kadane (DP)
- Grid Paths
- Unique Paths
- Minimum Path Sum
- 0/1 Knapsack
- Unbounded Knapsack
- Bounded Knapsack
- Subset Sum
- Equal Partition
- Target Sum
- Longest Common Subsequence - LCS
- Longest Common Substring
- Edit Distance
- Longest Palindromic Subsequence
- Palindrome Partitioning
- Longest Increasing Subsequence - LIS
- Number of LIS
- Maximum Sum Increasing Subsequence
- Matrix Chain Multiplication
- Burst Balloons
- Optimal BST
- Diameter (Tree DP)
- Tree Independent Set
- Traveling Salesman Problem
- Assignment Problems
- Counting Numbers (Digit DP)
- Digit Constraints