Longest Increasing Continuous subsequence II

http://lintcode.com/en/problem/longest-increasing-continuous-subsequence-ii/

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

        int n = A.length, m = A[0].length;
        int[][] dp1 = new int[n][m];

        flag = new boolean[n][m];

        for(int i = 0; i < n; i++){
            for(int j = 0; j < m; j++){
                dp1[i][j] = 1;
            }
        }

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

        return max;
    }

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

    private int checkAround(int[][] A, int i, int j, int[][] dp1){
        if(flag[i][j]){
            return dp1[i][j];
        }

        flag[i][j] = true;
        int n = A.length, m = A[0].length;
        int nx, ny;
        int max = 1;
        for(int x = 0; x < 4; x++){
            nx = i + dx[x];
            ny = j + dy[x];
            if(nx >= 0 && nx < n && ny >= 0 && ny < m){
                if(A[i][j] > A[nx][ny]){
                    max = Math.max(max, checkAround(A, nx, ny, dp1) + 1);
                }
            }
        }

        dp1[i][j] = max;
        return dp1[i][j];
    }
}

results matching ""

    No results matching ""