DFS Solution 16 ms


  • 0
    S
    public int longestIncreasingPath(int[][] matrix) {
        if(matrix == null || matrix.length == 0 || matrix[0] == null){
            return 0;
        }
    
        int[][] cache = new int[matrix.length][matrix[0].length];
        int max = 0;
        for(int i = 0; i < matrix.length; i++){
            for(int j = 0; j < matrix[0].length; j++){
                max = Math.max(max, longestIncreasingPath(i, j, null, cache, matrix));
            }
        }
        
        return max;
    }
    
    private int longestIncreasingPath(int row, int column, Integer preNum, int[][] cache, int[][] matrix){
        if(row < 0 || row >= matrix.length || column < 0 || column >= matrix[0].length){
            return 0;
        }
    
        if(preNum != null && preNum >= matrix[row][column]){
            return 0;
        }
        if(cache[row][column] != 0){
            return cache[row][column];
        }
        
        preNum = matrix[row][column];
        int up = longestIncreasingPath(row - 1, column, preNum,cache, matrix);
        int down = longestIncreasingPath(row + 1, column, preNum, cache, matrix);
        int left = longestIncreasingPath(row , column - 1, preNum, cache, matrix);
        int right = longestIncreasingPath(row , column + 1, preNum, cache, matrix);
        int localMax = Math.max(Math.max(up, down), Math.max(left, right)) + 1 ;
        cache[row][column] = localMax;
        return localMax;
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.