[LintCode] Longest Increasing Continuous subsequence II - Acjx - 博客园
http://shibaili.blogspot.com/2015/08/day-120-longest-increasing-subsequence.html
Longest Increasing Continuous subsequence I
[LintCode] Longest Increasing Continuous subsequence
Dynamic Programming, Time complexity = O(n^2)
f[i] = max(f[j] + 1) for all j < i and n[i] > n[j]
http://www.geeksforgeeks.org/longest-monotonically-increasing-subsequence-size-n-log-n/
http://www.csie.ntnu.edu.tw/~u91029/LongestIncreasingSubsequence.html
http://codeanytime.blogspot.com/2015/01/longest-increasing-subsequence.html
Read full article from [LintCode] Longest Increasing Continuous subsequence II - Acjx - 博客园
http://shibaili.blogspot.com/2015/08/day-120-longest-increasing-subsequence.html
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).
Example
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这道题使用dfs+dp，在dfs时更新状态，状态转移方程为 dp[(i,j)] = max(dp[(smaller neibors of all)]) + 1，来看代码：
public int longestIncreasingContinuousSubsequenceII(int[][] A) { int res = 0; if (A == null || A.length == 0 || A[0].length == 0) { return res; } int[][] store = new int[A.length][A[0].length]; for (int i = 0; i < A.length; i++) { for (int j = 0; j < A[0].length; j++) { if (store[i][j] == 0) { res = Math.max(res, dfs(A, store, i, j)); } } } return res; } private int dfs(int[][] a, int[][] store, int i, int j) { if (store[i][j] != 0) { return store[i][j]; } int left = 0, right = 0, up = 0, down = 0; if (j + 1 < a[0].length && a[i][j+1] > a[i][j]) { right = dfs(a, store, i, j+1); } if (j > 0 && a[i][j-1] > a[i][j]) { left = dfs(a, store, i, j-1); } if (i + 1 < a.length && a[i+1][j] > a[i][j]) { down = dfs(a, store, i+1, j); } if (i > 0 && a[i-1][j] > a[i][j]) { up = dfs(a, store, i-1, j); } store[i][j] = Math.max(Math.max(up, down), Math.max(left, right)) + 1; return store[i][j]; }[LintCode] Longest Increasing Continuous subsequence
Dynamic Programming, Time complexity = O(n^2)
f[i] = max(f[j] + 1) for all j < i and n[i] > n[j]
int longestIncreasingSubsequence(vector<int> nums) {
// write your code here
auto size = nums.size();
if (size==0) return 0;
vector<int> f(size, 1);
for(auto i=0;i<size;++i)
for(auto j=0;j<i;++j)
if(nums[i]>=nums[j])
f[i] = max(f[i], f[j]+1);
return *std::max_element(f.begin(), f.end());
}
Nlognhttp://www.geeksforgeeks.org/longest-monotonically-increasing-subsequence-size-n-log-n/
http://www.csie.ntnu.edu.tw/~u91029/LongestIncreasingSubsequence.html
http://codeanytime.blogspot.com/2015/01/longest-increasing-subsequence.html
int insert(vector<int> &A, int lastIndex, int target) {
int i = 0, j = lastIndex;
while(i <= j) {
int m = (i+j)/2;
if (A[m] > target)
j = m - 1;
else
i = m + 1;
}
A[i] = target;
return i;
}
int longestIncreasingSubsequence(vector<int> nums) {
int n = nums.size();
if (n < 2) return n;
vector<int> M(n, 0);
int longest = 0;
M[0] = nums[0];
for(int i =1; i < n; i++)
longest = max(longest, insert(M, longest, nums[i]));
return longest+1;
}
http://www.codedisqus.com/0mSegPVkXj/longest-increasing-subsequenceonlogn.htmlRead full article from [LintCode] Longest Increasing Continuous subsequence II - Acjx - 博客园
