最大路徑和基本資訊

最大路徑和是一種演算法，用於找出路徑，使得該路徑的元素（節點）之和大於任何其他路徑。

例如，我們有一個三角形，如下所示。

        3
      7   4
    2   4   6
  8   5   9   3

在上面的三角形中，找到具有最大總和的最大路徑。答案是，3 + 7 + 4 + 9 = 23

為了找到解決方案，我們一如既往地瞭解 Brute-Force 方法。Brute-Force 方法適用於這 4 行三角形，但考慮一個 100 或 100 行以上的三角形。因此，我們不能使用 Brute-Force 方法來解決這個問題。

讓我們轉向動態程式設計方法。

演算法：

對於三角形或二叉樹中的每個節點，最大路徑可以通過節點進行四種方式。

1. 僅限節點
2. 通過 Left Child + Node 的最大路徑
3. 通過右子節點的最大路徑
4. 通過右子節點的最大路徑+通過右子節點的最大路徑。

最大路徑和演算法示例：

空間輔助： O(n)
時間複雜度： O(n)