最长递增子序列 2D 矩阵递归

Question

我收到了一项新的作业任务，可以说让人有些沮丧。基本上，我需要创建一个二维整数数组，如下所示：

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填充了我的二维数组，这样我就不必担心边界问题，并使用嵌套的for循环遍历二维数组。在这些循环内部，我基本上检查N、NE、E、SE、S、SW、W、NW是否具有比当前元素更大的值。如果我惹怒了一些人，对不起，这是我第一次尝试发帖。如果您需要我发布一些代码，我会这样做的。非常感谢您的时间！

- Mike73

---

我不明白，你说的“最长上升子序列”是什么意思？ - Eng.Fouad

好的，在我上面发布的例子中，12、14、15、20、44、52、54、71、74、96 是一个递增的子序列。注意数字是严格按照递增顺序排列的。希望这可以帮助到你。 - Mike73

现在我明白了，似乎需要做很多工作。 - Eng.Fouad

这是一个相当棘手的问题。我假设您正在寻找最长子序列，而不考虑搜索方向？ - Perception

这似乎与最长路径问题有关，对于任意图形而言，该问题都是NP难的。 有人知道这个问题在平面图上是否是NP难的，或者更具体地说，是否是网格的子图？ - templatetypedef

@Perception正确。@templatetypedef不幸的是，我们在数据结构课程中还没有涵盖图形，尽管我听说很多人认为使用图形更容易解决此问题。 - Mike73

Answer 1

更新

我最近学习了动态规划，并且找到了一个更好的算法来解决这个问题。

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

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个周围点中的所有点。

证明

如果路径不以局部最小值开始，则起始点必须大于至少一个周围点，因此路径可以延伸。排除！因此，路径必须以局部最小值开始。同样的道理也适用于以局部最大值结尾的原因。

---

伪代码

对于所有局部最小值
  进行递归搜索
递归搜索 (点)
  如果点是局部最大值
    结束，并比较(必要时替换)最长路径
  否则
    对于所有更大的周围点
      进行递归搜索

- Dante May Code

---

Dante，非常感谢您深入的解释，我会尝试以这种方式实现。如果遇到任何困难，我会回来的。谢谢。 - Mike73

Answer 2

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

总时间：O(mn log(mn))用于排序矩阵条目，加上O(mn)用于查找最长路径。

- Irit Katriel

Answer 3

Java完整解决方案 它返回控制台路径，并返回最长序列，但您可以稍微修改此代码，然后您也可以获得最长路径

public class HedgehogProblemSolver {

private int rowCount;
private int columnCount;
private int[][] fieldArray;
private int maxApplesCount = 0;

public HedgehogProblemSolver(int inputArray[][]) {
    this.fieldArray = inputArray;
    rowCount = inputArray.length;
    columnCount = inputArray[0].length;
}

public int solveProblem() {
    findPathRecursive(0, 0, "", 0);
    System.out.println("Max apple count: " + maxApplesCount);
    return maxApplesCount;
}

private void findPathRecursive(int row, int column, String path, int applesCount) {
    if (row == rowCount - 1) {
        //last row
        for (int i = column; i < columnCount; i++) {
            //just go right until last column
            path += "-[" + fieldArray[row][i]  + "](" + row + ", " + i + ")";
            applesCount += fieldArray[row][i];
        }
        pathResult(path, applesCount);
        return;
    }
    if (column == columnCount - 1) {
        //last column
        for (int i = row; i <= rowCount - 1; i++) {
            //just go down until last row
            path += "-[" + fieldArray[i][column] + "](" + i + ", " + column + ")";
            applesCount += fieldArray[i][column];
        }
        pathResult(path, applesCount);
        return;
    }

    path = path + "-[" + fieldArray[row][column] + "](" + row + ", " + column + ")";
    applesCount += fieldArray[row][column];

    //go down
    findPathRecursive(row + 1, column, path, applesCount);
    //go right
    findPathRecursive(row, column + 1, path, applesCount);
}

private void pathResult(String path, int applesCount) {
    System.out.println("Path: " + path + "; apples: " + applesCount);
    if (applesCount > maxApplesCount) {
        maxApplesCount = applesCount;
    }
}

}

- Eugene Kisly

Answer 4

我知道这是一个非常古老的问题，但是我正在阅读Lubomir Stanchev的书，题为通过游戏学习Java，第14章项目就是那个精确的二维整数数组。任务是查找最长的递增序列，但只能在两个方向上进行，即南和东，没有对角线或其他任何方向。尽管如此，我还是花了几个小时才弄清楚逻辑，也不习惯使用递归。 我通过创建辅助方法简化了问题，检查下一个索引在该方向上是否有效（即不越界且大于当前值）。然后我将基本情况放在方法的开头，即当没有下一个可能的索引时。棘手的部分是字符串变量的赋值，因此每次方法使用递归时，索引都保存在字符串中。当存在多条可能路径时，我通过使用String.length()方法来比较每个序列的长度来解决它。 有了基本逻辑，要扩展该方法所需的全部就是在需要的方向上创建更多辅助方法，并将这些方向添加到逻辑中。

public static boolean isRightLegal(int[][] array, int row, int column) {
    //if we are at the last column
    if (column >= array[row].length - 1) {
        return false;
    }
    //if we are not at the one before last
    if ((column + 1) < array[row].length) {
        //if the current number is greater than the next
        if (array[row][column] > array[row][column + 1]) {
            return false;
        }
    }
    return true;
}

public static boolean isDownLegal(int[][] array, int row, int column) {
    //if we are at the last row
    if (row >= array.length - 1) {
        return false;
    }
    //if we are not at the one before last
    if ((row + 1) < array.length) {
        //if the current number is greater than the next
        if (array[row][column] > array[row + 1][column]) {
            return false;
        }
    }   
    return true;
}

public static String recursiveSequence(int[][] array, int row, int column, String path) {
    //base case: when we reach the end of the sequence
    if (! isDownLegal(array, row, column) && ! isRightLegal(array, row, column)) {
        return "(" + row + "," + column + ") ";
    }
    path = "(" + row + "," + column + ") ";
    //if both paths are valid
    if (isDownLegal(array, row, column) && isRightLegal(array, row, column)) {
        //calculate each sequence and pick the longest one
        if (recursiveSequence(array, (row + 1), column, path).length() > recursiveSequence(array, row, (column + 1), path).length()) {
            path += recursiveSequence(array, (row + 1), column, path);
        } else {
            path += recursiveSequence(array, row, (column + 1), path);
        }
        return path;
    }
    //if only the down path is valid
    if (isDownLegal(array, row, column)) {
        path += recursiveSequence(array, (row + 1), column, path);
    }
    //if only the right path is valid
    if (isRightLegal(array, row, column)) {
        path += recursiveSequence(array, row, (column + 1), path);
    }
    return path;
}

}

- Ricardo Ferreira Peñalver