给定一个整数矩阵（其中，有 n 行， m 列），请找出矩阵中的最长上升连续子序列。（最长上升连续子序列可从任意行或任意列开始，向上/下/左/右任意方向移动）。

您在真实的面试中是否遇到过这个题？

Yes

样例

给定一个矩阵

[
  [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]
]

返回25

搜索以某一点结尾的最长连续子序列

并且记录值。

public class Solution {
    /*
     * @param A: An integer matrix
     * @return: an integer
     */
    private int[] dx = {0,1,-1,0};
    private int[] dy = {1,0,0,-1};
    public int longestIncreasingContinuousSubsequenceII(int[][] A) {
        // write your code here
        if (A == null || A.length == 0) {
            return 0;
        }

        int[][] hash = new int[A.length][A[0].length];
        int ans = 0;
        for (int i = 0; i < A.length; i++) {
            for (int j = 0; j < A[0].length; j++) {
                hash[i][j] = dfs(A, hash, i, j);
                ans = Math.max(ans, hash[i][j]);
            }
        }
        return ans;
    }


    //recursively search the lis from n,m
    public int dfs(int[][] A, int[][] hash, int n, int m) {


        if (hash[n][m] != 0) {
            return hash[n][m];
        }


        int cur = 1;
        for (int i = 0; i < 4; i++) {
            int new_n = n + dx[i];
            int new_m = m + dy[i];
            if (new_n < 0 || new_m < 0 || new_n >= A.length || new_m >= A[0].length) {
                continue;
            }

            if (A[new_n][new_m] < A[n][m]) {
                cur = Math.max(cur, dfs(A, hash, new_n, new_m) + 1);    
            }
        }

        hash[n][m] = cur;
        return cur;
    }
}