Longest Increasing Continuous subsequence II
http://lintcode.com/en/problem/longest-increasing-continuous-subsequence-ii/
public class Solution {
/*
* @param : An integer matrix
* @return: an integer
*/
boolean[][] flag;
public int longestIncreasingContinuousSubsequenceII(int[][] A) {
// write your code here
if(A == null || A.length == 0){
return 0;
}
int n = A.length, m = A[0].length;
int[][] dp1 = new int[n][m];
flag = new boolean[n][m];
for(int i = 0; i < n; i++){
for(int j = 0; j < m; j++){
dp1[i][j] = 1;
}
}
int max = 1;
for(int i = 0; i < n; i++){
for(int j = 0; j < m; j++){
max = Math.max(max, checkAround(A, i, j, dp1));
}
}
return max;
}
int[] dx = {1, 0, 0, -1};
int[] dy = {0, 1, -1, 0};
private int checkAround(int[][] A, int i, int j, int[][] dp1){
if(flag[i][j]){
return dp1[i][j];
}
flag[i][j] = true;
int n = A.length, m = A[0].length;
int nx, ny;
int max = 1;
for(int x = 0; x < 4; x++){
nx = i + dx[x];
ny = j + dy[x];
if(nx >= 0 && nx < n && ny >= 0 && ny < m){
if(A[i][j] > A[nx][ny]){
max = Math.max(max, checkAround(A, nx, ny, dp1) + 1);
}
}
}
dp1[i][j] = max;
return dp1[i][j];
}
}