Copy public class Solution {
/**
* @param A an array of Integer
* @return an integer
*/
public int longestIncreasingContinuousSubsequence ( int [] A) {
// Write your code here
if (A == null || A . length == 0 ) return 0 ;
int max = 1 ;
int cur = 1 ;
for ( int i = 1 ; i < A . length ; i ++ ){
if ( A [i] > A [i - 1 ]){
cur ++ ;
max = Math . max (max , cur);
} else {
cur = 1 ;
}
}
cur = 1 ;
for ( int i = A . length - 2 ; i >= 0 ; i -- ){
if ( A [i] > A [i + 1 ]){
cur ++ ;
max = Math . max (max , cur);
} else {
cur = 1 ;
}
}
return max;
}
}
去年的 Google 高频题,著名的 POJ 1088 - 滑雪。当时在论坛里看到这道题的时候,觉得完全没思路,也不知道自己什么时候能独立当场把这道题做出来。
这题是 2D-array 上的搜索问题,参考 number of islands 和 word search.
Copy public class Solution {
public int longestIncreasingPath ( int [][] matrix) {
if (matrix == null || matrix . length == 0 ) return 0 ;
int rows = matrix . length ;
int cols = matrix[ 0 ] . length ;
int [] dp = new int [rows * cols];
int max = 0 ;
for ( int i = 0 ; i < rows; i ++ ){
for ( int j = 0 ; j < cols; j ++ ){
max = Math . max (max , memoizedSearch(i , j , cols , rows , matrix , dp) );
}
}
return max;
}
private int memoizedSearch ( int x , int y , int cols , int rows ,
int [][] matrix , int [] dp){
if (x < 0 || x >= rows) return 0 ;
if (y < 0 || y >= cols) return 0 ;
int index = x * cols + y;
if (dp[index] != 0 ) return dp[index];
int left = 0 , right = 0 ;
int top = 0 , bottom = 0 ;
if (y - 1 >= 0 && matrix[x][y - 1 ] > matrix[x][y]) left = memoizedSearch(x , y - 1 , cols , rows , matrix , dp) ;
if (y + 1 < cols && matrix[x][y + 1 ] > matrix[x][y]) right = memoizedSearch(x , y + 1 , cols , rows , matrix , dp) ;
if (x - 1 >= 0 && matrix[x - 1 ][y] > matrix[x][y]) top = memoizedSearch(x - 1 , y , cols , rows , matrix , dp) ;
if (x + 1 < rows && matrix[x + 1 ][y] > matrix[x][y]) bottom = memoizedSearch(x + 1 , y , cols , rows , matrix , dp) ;
int maxLR = Math . max (left , right) + 1 ;
int maxTB = Math . max (top , bottom) + 1 ;
int max = Math . max (maxLR , maxTB);
dp[index] = max;
return max;
}
}