java - 在二维数组中找到最长的递增子序列

Question

我把这个问题作为作业，但我真的不知道从哪里开始。我已经使用递归算法(#1)实现了解决方案，但我就是想不通如何使用堆栈解决问题……任何帮助都会很棒。

在 15 x 15 数组中找到最长的递增数字序列。例如，如果数组 4x4 包含

97  47  56  36
35  57  41  13
89  36  98  75
25  45  26  17

那么最长的递增数列就是长度为8的数列，由17、26、36、41、47、56、57、97组成。注意递增数列中没有重复。

1. 设计一个递归算法来解决这个问题并用Java实现。

2. 设计一个非递归算法来使用堆栈解决相同的问题。

Answer 1

因为这是作业，这里有一个提示:您可以将数字数组转换为有向无环图。 (它是非循环的，因为序列中不允许重复。)之后，您可以使用算法解决最长路径问题，在您的图中找到最大长度的简单路径。