如何在 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 没有关联。

您也可以 select 一行中只有一个数字。你不能去 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 指出的那样，通过遵循从顶部开始的三个可能子节点的最大总和，您在累积树中获得了最佳路径。

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

  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] 的值。

Answer 2

一个选项是通过放置相关边来准备有向图，添加汇节点和运行 Dijkstra 从 1 到汇节点。虽然不会是线性的（汇节点是连接到 7 8 9 10 的节点）另一个解决方案可能是动态规划，自下而上（在第一个答案中描述）或自上而下

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

How to get the biggest sum in 2D array in O(n)?

java

arrays

algorithm

multidimensional-array