一、LIS最长上升子序列
解法有O(n^2)的DP，O(nlogn)的二分+贪心法，以及O(nlogn)的树状数组优化的DP
只介绍最简单的dp
for (int j = n - 1; j >= 0; j--){
for (int k = j + 1; k < n; k++)
if (a[j] < a[k])
dp[j] = max(dp[k] + 1, dp[j]);
}
int m = 0;
for (int j = 0; j <= n; j++){
m = max(m, dp[j]);
}
printf("\n%d", m);
dp[j] 代表以第 j 个数为序列头部的最长上升序列
二、LCS最长公共子序列
for (i = 1; i <= lena; i++){
for (j = 1; j <= lenb; j++){
if (a[i - 1] == b[j - 1]){
dp[i][j] = dp[i - 1][j - 1] + 1;
}
else{
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
}
}
}
printf("%d\n", dp[lena][lenb]);
