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

Challenge:

O(nm) time and memory.

Code:

This problem can be easily solved by Depth First Search. However, this solution will have O(1) space complexity and O(2^{nm}) time complexity. This is not feasible for solving large matrix, even the matrix is only as LARGE as 8x8. Therefore, we need to improve the time complexity to O(mn) with a trade off of m * n memory space. We use this additional space to store the solution for previous search. When current step needs to find the solution for a branch, we could check the memory wether this branch has been calculated or not. If this branch is calculated, we just return the solution with O(1) time.

Solution:

public class Solution {
    /**
     * @param A an integer matrix
     * @return  an integer
     */
    public int longestIncreasingContinuousSubsequenceII(int[][] A) {
        if (A == null || A.length == 0 || A[0].length == 0) {
            return 0;
        }
        int m = A.length;
        int n = A[0].length;
        int[][] memory = new int[m][n];
        int res = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                res = Math.max(res, dfs(i, j, A, memory));
            }
        }
        return res;
    }

    private static int[] dx = {1, -1, 0, 0};
    private static int[] dy = {0, 0, 1, -1};

    private int dfs(int i, int j, int[][] A, int[][] memory) {
        if (memory[i][j] > 0) {
            return memory[i][j];
        }
        for (int k = 0; k < 4; k++) {
            int nx = i + dx[k];
            int ny = j + dy[k];
            if (nx < 0 || nx >= A.length || ny < 0 || ny >= A[0].length) {
                continue;
            }
            if (A[i][j] < A[nx][ny]) {
                memory[i][j] = Math.max(memory[i][j], dfs(nx, ny, A, memory));
            }
        }
        memory[i][j] = memory[i][j] + 1;
        return memory[i][j];
    }
}