Untitled

public class LongestIncreasingPath {

    public static int longestIncreasingPath(int[][] matrix) {
        int m = matrix.length;
        int n = matrix[0].length;
        int[][] memo = new int[m][n]; // Memoization array to store results
        int maxPath = 0;

        // Iterate over all cells to find the maximum increasing path
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                maxPath = Math.max(maxPath, dfs(matrix, i, j, memo));
            }
        }
        return maxPath;
    }

    private static int dfs(int[][] matrix, int row, int col, int[][] memo) {
        // If already computed, return the memoized result
        if (memo[row][col] != 0) {
            return memo[row][col];
        }

        int m = matrix.length;
        int n = matrix[0].length;
        int maxLength = 1; // Start with length 1 for the current cell

        // Directions: up, down, left, right
        int[][] directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

        for (int[] dir : directions) {
            int newRow = row + dir[0];
            int newCol = col + dir[1];

            // Move to the new cell if it's within bounds and greater than the current cell
            if (newRow >= 0 && newRow < m && newCol >= 0 && newCol < n && matrix[newRow][newCol] > matrix[row][col]) {
                int pathLength = 1 + dfs(matrix, newRow, newCol, memo);
                maxLength = Math.max(maxLength, pathLength);
            }
        }

        // Store the result in the memoization array
        memo[row][col] = maxLength;

        return maxLength;
    }

    public static void main(String[] args) {
        int[][] matrix1 = {{9, 9, 4}, {6, 6, 8}, {2, 1, 1}};
        System.out.println(longestIncreasingPath(matrix1)); // Output: 4

        int[][] matrix2 = {{3, 4, 5}, {3, 2, 6}, {2, 2, 1}};
        System.out.println(longestIncreasingPath(matrix2)); // Output: 4

        int[][] matrix3 = {{1}};
        System.out.println(longestIncreasingPath(matrix3)); // Output: 1
    }
}