最长递增序列 2D 矩阵递归更新递归提示伪代码

algorithm java recursion

2022-09-03 01:02:23

我收到了一个新的家庭作业，至少可以说这有点令人沮丧。基本上，我有一个2D整数数组，如下所示：

97 47 56 36 60 31 57 54 12 55 
35 57 41 13 82 80 71 93 31 62 
89 36 98 75 91 46 95 53 37 99 
25 45 26 17 15 82 80 73 96 17 
75 22 63 96 96 36 64 31 99 86 
12 80 42 74 54 14 93 17 14 55 
14 15 20 71 34 50 22 60 32 41 
90 69 44 52 54 73 20 12 55 52 
39 33 25 31 76 45 44 84 90 52 
94 35 55 24 41 63 87 93 79 24

我将编写一个递归方法，或者像你一样编写函数，以计算最长递增的子序列。在此示例中，最长递增的子序列如下：

(5,0)   with value 12
(6,0)   with value 14
(6,1)   with value 15
(6,2)   with value 20
(7,2)   with value 44
(7,3)   with value 52
(7,4)   with value 54
(6,3)   with value 71
(5,3)   with value 74
(4,3)   with value 96

因此，我不仅要检查N，S，E，W的值是否严格更大，而且还必须考虑对角线。我已经对如何递归地解决这个问题进行了广泛的研究，但是我没有太多的运气，递归是我最弱的科目（是的，我知道它在某些情况下有多强大）。我看过类似的东西，有人提到了一个丙烯酸图表，但这不是我想要的。

到目前为止，我基本上已经用0填充了我的2D数组，这样我就不必担心边界，并且我使用嵌套的for循环来遍历2D数组。在这些循环中，我基本上是在检查N，NE，E，SE，S，SW，W，NW的值是否大于当前元素。对不起，如果我让你们中的一些人感到不安，这是我第一次尝试发帖。如果您需要我发布一些代码，我会这样做。非常感谢您抽出宝贵时间接受采访！

答案 1

更新

我最近学习了动态编程，并且为这个问题找到了更好的算法。

算法很简单：找到每个点的最长长度，并将结果记录在2D数组中，这样我们就不需要再次计算某些点的最长长度。

int original[m][n] = {...};
int longest[m][n] = {0};

int find() {
    int max = 0;
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            int current = findfor(i, j);
            if (current > max) { max = current; }
        }
    }
    return max;
}

int findfor(int i, int j) {
    if (longest[i][j] == 0) {
        int max = 0;
        for (int k = -1; k <= 1; k++) {
            for (int l = -1; l <= 1; l++) {
                if (!(k == 0 && l == 0) &&
                    i + k >= 0 && i + k < m &&
                    j + l >= 0 && j + l < n &&
                    original[i + k][j + l] > original[i][j]
                   )
                    int current = findfor(i + k, j + l);
                    if (current > max) { max = current; }
                }
            }
        }
        longest[i][j] = max + 1;
    }
    return longest[i][j];
}

递归

1）从一个点开始（并且必须对所有必要的点采取此步骤）

2）如果没有更大的周围点，则此路径结束;否则选择一个更大的周围点继续路径，然后转到2）。

2.1）如果（结束的）路径长于记录的最长路径，则将自身替换为最长路径。

提示

（更少的计算，但更多的编码）

对于最长路径，其起点将是局部最小点，其终点将是局部最大点。

局部最小值，小于（或等于）所有（最多）8 个周围点。

局部最大值，大于（或等于）所有（最多）8 个周围点。

证明

如果路径不以局部最小值开始，则起点必须至少大于周围的点，因此可以扩展路径。拒绝！因此，路径必须以局部最小值开头。类似的原因以局部最大值结尾。

伪代码

for all local minimum
  do a recursive_search

recursive_search (point)
  if point is local maximum
    end, and compare (and substitute if necessary) longest
  else
    for all greater surrounding points
      do a recursive_search

答案 2

另一种方法是：按矩阵条目中的值对矩阵条目进行排序。从最大迭代到最小。对于每个条目，计算恒定时间内的最长路径：对于较大的邻居（已计算），最长路径为 1 + 最长路径的最大值。

总时间：O（mn log（mn）））对矩阵条目进行排序，加上O（mn）查找最长路径。