Java 2 dim dp array beats 90.59%


  • 0
    A
    public class Solution {
    public static int longestIncreasingPath(int[][] matrix) {
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) return 0;
        int[][] memo = new int[matrix.length][matrix[0].length];
    
        int max = Integer.MIN_VALUE;
    
        for (int r=0; r<memo.length; r++)
            for (int c=0; c<memo[r].length; c++)
                memo[r][c] = -1;
    
        for (int r=0; r<matrix.length; r++)
            for (int c=0; c<matrix[r].length; c++)
                max = Math.max(max, longestIncreasingPath(matrix, r, c, Integer.MIN_VALUE, memo));
    
        return max;
    }
    
    private static int longestIncreasingPath(int[][] matrix, int r, int c, int previous, int[][] memo) {
        if (r < 0 || r >= matrix.length || c < 0 || c >= matrix[r].length || matrix[r][c] <= previous) return 0;
        else if (memo[r][c] != -1) return memo[r][c];
        else {
            memo[r][c] = Math.max(
                    1 + longestIncreasingPath(matrix, r - 1, c, matrix[r][c], memo),
                    Math.max(
                            1 + longestIncreasingPath(matrix, r + 1, c, matrix[r][c], memo),
                            Math.max(
                                    1 + longestIncreasingPath(matrix, r, c - 1, matrix[r][c], memo),
                                    1 + longestIncreasingPath(matrix, r, c + 1, matrix[r][c], memo)
                            )
                    )
            );
            return memo[r][c];
        }
    }
    

    }


Log in to reply
 

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