Give you an integer matrix (with row size n, column size m)，find the longest increasing continuous subsequence in this matrix. (The definition of the longest increasing continuous subsequence here can start at any row or column and go up/down/right/left any direction).
Given a matrix:
[
[1 ,2 ,3 ,4 ,5],
[16,17,24,23,6],
[15,18,25,22,7],
[14,19,20,21,8],
[13,12,11,10,9]
]
return 25
O(nm) time and memory.
SOLUTION:
第一步，问最大／最小问题，往DP方向去考虑。
DP：就是看状态，转移方程，初始化，定义最后结果。
状态：可以定义为 f(x,y) = 以(x,y)结尾，的最大LICS。
转移方程：四个方向dp，不太好弄，并且初始值可能在中间某个位置，不好找。发现这种情况，果断的用记忆化搜索，递归去做。
第二步，记忆化搜索：
首先画一个递归树 （x，y）
/ / \ \
上(x-1,y) 下(x+1,y) 左(x,y-1) 右(x,y+1)
对于这个题，就是有一个点，向四周递归，但是下一步继续递归的时候，会重复计算(x,y)点，所以要用一个dp[][]数组纪录下结果，并且用一个flag[][]数组纪录这个点是否被计算过，如果计算过就可以直接返回答案。
递归就需要用一个search()辅助函数,对这个辅助函数，定义的interface是这个点的坐标，以及之前给的原始数组信息A[][]。
search(int x, int y, int[][] A){...
if ( A[x][y] was visited ){
return dp[x][y];
}
for ( from 上 to 下 to 左 to 右){
if (up/down/left/right < A[x][y]){
dp[x][y] = dp[up/down/left/right] + 1;
}
}
ans = dp[x][y];
return ans;
}
在代码中有很多全局变量，目的是方便传递到辅助函数里。做辅助函数interface时候，只要满足基本要求的传入参数就可以。
辅助函数就是这个逻辑，然后具体看代码：
public class Solution { /** * @param A an integer matrix * @return an integer */ private int m; private int n; private int[][] result; private int[][] flag; public int longestIncreasingContinuousSubsequenceII(int[][] A) { if (A.length == 0){ return 0; } m = A.length; n = A[0].length; int max = 1; result = new int[m][n]; flag = new int[m][n]; for (int i = 0; i < m; i++){ for (int j = 0; j < n; j++){ result[i][j] = search(i, j, A); max = Math.max(max, result[i][j]); } } return max; } private int[] dx = {1, -1, 0, 0}; private int[] dy = {0, 0, 1, -1}; private int search(int x, int y, int[][] A){ if (flag[x][y] != 0){ return result[x][y]; } int nx, ny; int ans = 1; for (int i = 0; i < 4; i++){ nx = x + dx[i]; ny = y + dy[i]; if (nx >= 0 && nx < m && ny >= 0 && ny < n){ if (A[x][y] > A[nx][ny]){ ans = Math.max(ans, search(nx, ny, A) + 1); } } } flag[x][y] = 1; result[x][y] = ans;; return ans; } }
[LintCode] Longest Increasing Continuous subsequence II
原文：http://www.cnblogs.com/tritritri/p/4952157.html
