Tuesday, April 25, 2017

Longest Increasing Continuous subsequence II

public class Solution {
    /**
     * @param A an integer matrix
     * @return  an integer
     */
    public int longestIncreasingContinuousSubsequenceII(int[][] A) {
        // Write your code here
        if (A == null || A.length == 0 || A[0] == null || A[0].length == 0) return 0;
        int rows = A.length, cols = A[0].length;
        int maxLength = 0;
        dp = new int[rows][cols];
        visited = new boolean[rows][cols];
        for (int x = 0; x < rows; x++) {
            for (int y = 0; y < cols; y++) {
                maxLength = Math.max(maxLength, search(A, x, y));
            }
        }
        return maxLength;
    }
    private int[][] dp;
    private boolean[][] visited;
    private int[] dx = {1, 0, -1, 0};
    private int[] dy = {0, 1, 0, -1};
    //The max length of path starting from current point (x,y)
    private int search(int[][] A, int x, int y) {
        if (visited[x][y]) return dp[x][y];
        int currMax = 0;
        //Traverse its neighbors
        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            if (nx < 0 || nx >= A.length || ny < 0 || ny >= A[0].length) continue;
            if (A[nx][ny] > A[x][y]) {
                currMax = Math.max(currMax, search(A, nx, ny));
            }
        }
        dp[x][y] = currMax + 1;
        visited[x][y] = true;
        return dp[x][y];
    }
}

No comments:

Post a Comment