题目链接：/zh-cn/problem/longest-increasing-continuous-subsequence-ii/
最长上升连续子序列 II
给定一个整数矩阵（其中，有 n 行， m 列），请找出矩阵中的最长上升连续子序列。（最长上升连续子序列可从任意行或任意列开始，向上/下/左/右任意方向移动）。
样例
给定一个矩阵
[[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]]
返回25
思路：记忆化搜索 + dp
设Lics(num)表示以num开头的最长上升子连续序列的长度， 则Lics(A[x][y]) = max(Lics(A[x-1][y]), Lics(A[x][y-1]),Lics(x+1,y),Lics(x, y+1))+1;
#include<iostream> #include<cstdio>#include<cstring>#include<algorithm>#include<vector>#include<deque>#include<map> using namespace std;class Solution {public:/*** @param A an integer matrix* @return an integer*/int n, m, maxL;int lics[1000][1000];int vis[1000][1000];int dir[4][2] = {{0, 1}, {1, 0}, {0,-1}, {-1,0}};int dfs(vector<vector<int>>& A, int x, int y){int maxLics = 0;vis[x][y] = 1;for(int i=0; i<4; ++i){int xx = x+dir[i][0];int yy = y+dir[i][1];if(xx<0 || yy<0 || xx>=n || yy>=m) continue;if(A[x][y] >= A[xx][yy]) continue;if(!vis[xx][yy])maxLics = max(maxLics, dfs(A, xx, yy));elsemaxLics = max(maxLics, lics[xx][yy]);}lics[x][y] = maxLics+1;if(maxL < lics[x][y]) maxL = lics[x][y];return lics[x][y];} int longestIncreasingContinuousSubsequenceII(vector<vector<int>>& A) {n = A.size();if(n == 0) return 0;m = A[0].size();memset(lics, 0, sizeof(lics));memset(vis, 0, sizeof(vis));maxL = 0;for(int i=0; i<n; ++i)for(int j=0; j<m; ++j)if(!vis[i][j])dfs(A, i, j);return maxL;}};/*1 2 3 4 516 17 24 23 615 18 25 22 714 19 20 21 813 12 11 10 9*/
如果觉得《lintcode 最长上升连续子序列 II(二维最长上升连续序列)》对你有帮助，请点赞、收藏，并留下你的观点哦！
