p*********g
发帖数: 116 | 5 DP + DFS
public class Solution {
/**
* @param A an integer matrix
* @return an integer
*/
int max = 0;
public int longestIncreasingContinuousSubsequenceII(int[][] A) {
// Write your code here
if (A == null || A.length == 0 || A[0].length == 0)
return 0;
int n = A.length;
int m = A[0].length;
int[][] L =new int[n][m];
int max = 0;
for (int i=0; i
for (int j=0; j
if (L[i][j] == 0)
dfs( A, L, i, j, n, m );
}
}
return this.max;
}
private int dfs(int[][] A, int[][] L, int i, int j, int n, int m){
if (L[i][j]>0) {
return L[i][j];
}
int x = A[i][j];
int[] d = new int[4];
if ( j-1 >=0 && A[i][j-1] > x )
d[0] = dfs(A,L,i, j-1, n, m);
if ( j+1 < m && A[i][j+1] > x )
d[1] = dfs(A,L,i, j+1, n, m);
if ( i-1 >=0 && A[i-1][j] > x )
d[2] = dfs(A,L,i-1, j, n, m);
if ( i+1 < n && A[i+1][j] > x )
d[3] = dfs(A,L,i+1, j, n, m);
L[i][j] = 1+Math.max( Math.max(d[0],d[1]) , Math.max(d[2],d[3]) );
if (L[i][j] > this.max)
this.max = L[i][j];
return L[i][j];
}
} |
