Longest Increasing Continuous subsequence II

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

DP Solution:

1. Memory Search
2. State: f[i][j] the maximal number at (i, j)
3. Function: find 4 directions which meet the condition A[x][y] < A[i][j], f[i][j] = max(f[i][j], search(x, y))
4. Initial: loop i, j
5. Answer: max

    private int[] dx = {0, 0, 1, -1};
    private int[] dy = {1, -1, 0, 0};
    public int longestIncreasingContinuousSubsequenceII(int[][] A) {
        if (A == null || A.length == 0 || A[0] == null || A[0].length == 0) {
            return 0;
        }

        int m = A.length;
        int n = A[0].length;

        int[][] f = new int[m][n];

        int max = 1; 
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                max = Math.max(max, search(A, f, i, j));       
            }
        }

        return max;
    }

    private int search(int[][] A, int[][] f, int i, int j) {
        if (f[i][j] > 0) {
            return f[i][j];
        }

        f[i][j] = 1;

        for (int k = 0; k < 4; ++k) {
            int x = i + dx[k];
            int y = j + dy[k];
            if (x >= 0 && x < A.length && y >= 0 && y < A[0].length && A[x][y] < A[i][j]) {
                f[i][j] = Math.max(f[i][j], search(A, f, x, y)+1);
            }
        }

        return f[i][j];
    }