最大路径和基本信息

最大路径和是一种算法，用于找出路径，使得该路径的元素（节点）之和大于任何其他路径。

例如，我们有一个三角形，如下所示。

        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)