如何在 O(n) 中获得二维数组中的最大和？

Question

我需要计算二维数组中可能的最大和，但代码必须是 O(n) 的效率。n 是我们在数组中的数字数量。

数组就像楼梯，用户只需要输入N个数字。我们不需要检查它是否是一个有效的数字。

数字将显示在数组中，如下所示：

1

2 3

4 5 6

7 8 9 10

每一行都有一个数字。

您需要从第一行或最后一行开始获得最大的总和路径。在每次迭代中，您只能向下移动一步，或对角向下和向左/向下和向右移动一步。

这意味着如果你从第一行开始，你可以去 2 或 3。假设你去 2；现在你只能去 4 或 5。如果你选择 5，你可以去 7 或 8 或 9。或者如果你想你可以去 1 > 3 > 6 > 8。但你不能去 1 > 2 > 6 > 10 因为 2 与 6 无关。

您也可以在一行中只选择一个数字。你不能 1 > 2 > 3 > 6 > 8 > 9 > 10 或类似的东西。

我们也可以改变一个单元格的值，但路径必须相同。这意味着我可以将例如 9 更改为 50，但这不会很好，因为它不是原始数组中的好路径。（这个数组中的最大总和路径 1 > 3 > 6 > 10，所以我不能去不同的单元格）

我的问题是我需要这段代码以 O(n) 的效率运行。

我试图从最后一行开始检查它可以走的每一条有效路径，我试图在每种可能性中寻找最大的数字。第一个不是 O(n) 效率，第二个可能会得到错误的答案。

我也尝试从第一行开始并扫描和比较所有步骤，但同样不是 O(n) 效率。

只是为了确保，我并没有要求任何人为我编写代码，只是为了帮助我找出计算它的最佳方法。

顺便说一句，看到很少的评论并想在最后补充一点，我需要打印最大路径总和，而不是路径本身。

Answer 1

您可以自下而上确定最大总和。例如，最下面的两行是：

  4   5   6
 / \ / \ / \
7   8   9  10

现在将最大可能总和累积到第二行但最后一行：

 12  14  16
 / \ / \ / \
7   8   9  10

例如，节点 4 处的 7 或 8 的最大值是 12。继续此操作，但使用 max-sum 值，直到顶部：

     20
     / \
   16  19
   / \ / \
 12  14  16
 / \ / \ / \
7   8   9  10

顶部节点现在具有最大可能的总和：1 + 3 + 6 + 10 == 20。这种方法将破坏原始数据（因为它用最大总和覆盖了它）并且它不会给你路径，只有最大和的值。

在这里，三角形数组看起来像一棵树，但您并没有真正构建一棵树：链接可以很容易地通过它们的位置来描述。

编辑：我现在意识到这并不能完全解决您的问题，因为它省略了向左可能的步骤，但原则仍然是好的：自下而上累积最大可能的子和，除了您需要考虑下面的三个值，不仅仅是两个。（我有点不愿意重绘 ASCII 树。:-)

编辑二：正如@rpattiso 指出的那样，通过遵循从顶部开始的三个可能子节点的最大总和，您在累积树中获得了最佳路径。

编辑 III：当您将矩阵视为楼梯并考虑每个节点的三个子节点时，图形变为：

  20
   | \
  16  19
   | X | \
  12  14  16
   | X | X | \
   7   8   9  10

这里的X意思是两条交叉路径。请注意，第一列是一个特例，因为该列中的节点只有两个子节点。

如果m是行n = m*(m + 1)/2数， 是单元格数，并且如果您的数组由二维 C 样式数组表示a[row][col]，则您的最大和算法为：

int row = m - 1;

while (row--) {        
    a[row][0] += max(a[row + 1][0], a[row + 1][1]);

    for (int col = 1; col < row + 1; col++) {
        int a1 = a[row + 1][col - 1];
        int a2 = a[row + 1][col];
        int a3 = a[row + 1][col + 1];

        a[row][col] += max(a1, a2, a3);
    }
}

您的最大总和是 的值a[0][0]。