LongestIncreasing Continuous Subsequence II

Problem

Give you an integer matrix (with row size n, column size m)，find the longest increasing continuous subsequence in this matrix. (The definition of the longest increasing continuous subsequence here can start at any row or column and go up/down/right/left any direction). Example

Given a matrix:

[
  [1 ,2 ,3 ,4 ,5],
  [16,17,24,23,6],
  [15,18,25,22,7],
  [14,19,20,21,8],
  [13,12,11,10,9]
]

return 25 Challenge

O(nm) time and memory.

解题思路

解决方法都是DFS + Memorization. dp[i][j]表示以点(i, j)为起始点 的连续子序列最大长度。 dp[i][j]的值可以根据其符合要求的邻居的dp值推出，根据dp值，我们维护一个全局的最大值

根据记忆化存储的通用方法，这里可以以结果是否为0(初始化为0时)来进行区分。

public int longestIncreasingContinuousSubsequenceII(int[][] A) {
    if (A == null || A.length == 0 || A[0].length == 0) return 0;

    int max = 0;
    int[][] dp = new int[A.length][A[0].length];
    for (int row = 0; row < A.length; row++) {
        for (int col = 0; col < A[0].length; col++) {
            if (dp[row][col] == 0) {
                max = Math.max(max, dfs(A, row, col, dp));
            }
        }
    }

    return max;
}

private int dfs(int[][] A, int row, int col, int[][] dp) {
    if (dp[row][col] != 0) {
        return dp[row][col];
    }

    int[][] dirs = new int[][]{{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
    int max = 0;

    // 对符合要求的邻居分别DFS
    for (int i = 0; i < dirs.length; i++) {
        int x = row + dirs[i][0];
        int y = col + dirs[i][1];
        if (x >= 0 && x < dp.length && y >= 0 && y < dp[0].length && A[x][y] > A[row][col]) {
            dfs(A, x, y,dp);
            max = Math.max(max, dp[x][y]);
        }
    }

    // return maximum of up, down, left, right
    dp[row][col] = 1 + max;

    return dp[row][col];
}

References

1 solution from segmentfault

2 solution from kancloud