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