java - 如何在 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。继续此操作，但使用最大和值，直到顶部:

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

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

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

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

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

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

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

这里，X 表示两条交叉路径。请注意，第一列是一种特殊情况，因为该列中的节点只有两个子节点。

如果 m 是行数并且 n = m*(m + 1)/2 是单元格数并且如果您的数组由两个表示-dimensional C-style array 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] 的值。