题目是看到有人给出阿里的一道编程题，自己就试了试。
题目链接：https://blog.csdn.net/spicyfish/article/details/76017423
参考链接：http://qiemengdao.iteye.com/blog/1660229
给定两个数列a，b，求这两个数列的最大公共子序列长度。
如a={2,1,6,3,10,7}，b={1,10,7,13}，
则最长公共子序列为{1,10,7}，长度为3。
动态规划的思想。
假定两个序列为X={x1, x2, …, xm}和Y={y1, y2, …, yn)，并设Z={z1, z2, …, zk}为X和Y的任意一个LCS。
如果xm = yn，则zk = xm=yn，且Zk-1是Xm-1和Yn-1的一个LCS。
如果xm != yn, 则zk != xm，说明Z是Xm-1和Y得一个LCS。
如果xm != yn, 则zk != yn，说明Z是X和Yn-1的一个LCS。
借参考链接图：
废话不多说，上代码：
// 最长公共子序列问题 // 动态规划O(N^2) int commonsub(vector<int>a, vector<int>b) { vector<vector<int>>len(a.size() + 1, vector<int>(a.size() + 1)); for (int i = 0; i < len.size(); i++) { len[i][0] = 0; len[0][i] = 0; } for (int i = 1; i < len.size();i++) { for (int j = 1; j < len.size();j++) { if (a[i - 1] == b[j - 1]) { len[i][j] = len[i - 1][j - 1] + 1; } else len[i][j] = mymax(len[i - 1][j], len[i][j - 1]); } } return len[a.size()][a.size()]; }给定序列a={5,6,7,1,2,8}，求最大的递增子序列长度。
{5,6,7,8}是最大递增子序列，长度为4。
原序列是a，将a排序后的序列称为b，则求a中最大递增子序列就是求a与b的最大公共子序列。
如a={5,6,7,1,2,8}， b={1,2,5,6,7,8}。则两者的最大公共子序列就是{5,6,7,8}，长度是4。
代码：
int commonsub(vector<int>a, vector<int>b) { vector<vector<int>>len(a.size() + 1, vector<int>(a.size() + 1)); for (int i = 0; i < len.size(); i++) { len[i][0] = 0; len[0][i] = 0; } for (int i = 1; i < len.size();i++) { for (int j = 1; j < len.size();j++) { if (a[i - 1] == b[j - 1]) { len[i][j] = len[i - 1][j - 1] + 1; } else len[i][j] = mymax(len[i - 1][j], len[i][j - 1]); } } return len[a.size()][a.size()]; } int main() { vector<int>a = { 5, 6, 7, 1, 2, 8 }; //方法一： vector<int>b = a; sort(b.begin(), b.end()); cout << "-----------this is the first mathod's result---------" << endl; cout << commonsub(a, b) << endl; system("pause"); return 0; }维护一个数组b，长度与a数组长度相同，b数组中存放的是以a数组的每个元素为结尾的最大递增子序列的长度。
如a={5,6,7,1,2,8}，
则b[0]=1，表示以5结尾的最大递增子序列长度为1，
b[1]=2，表示以6结尾的最大递增子序列长度为2，
b[2]=3，表示以7结尾的最大递增子序列长度为3，
b[3]=1，表示以1结尾的最大递增子序列长度为1，
b[4]=2，表示以2结尾的最大递增子序列长度为2，
b[5]=4，表示以6结尾的最大递增子序列长度为4。
代码：
int maxup(vector<int>a) { vector<int>len(a.size(), 1); for (int i = 1; i < a.size();i++) { for (int j = i - 1; j >= 0;j--) { if (a[i]>a[j] && len[i] < len[j] + 1) len[i] = len[j] + 1; } } int max = len[0]; for (int i = 1; i < len.size();i++) { if (max < len[i]) max = len[i]; } return max; } int main() { vector<int>a = { 5, 6, 7, 1, 2, 8 }; //方法二： cout << "-----------this is the second mathod's result---------" << endl; cout << maxup(a) << endl; system("pause"); return 0; }已知a={5,6,7,1,2,8}，则我们可以看出a的最大递增子序列长度是4，现在我们构造一个数组b，里面每个元素存放了每个长度下的最小末尾数是多少。b数组是有序的。
如，刚开始，a[0]=5，b[0]=5，说明长度是1时，递增子序列的最小末尾是5，
a[1]=6，6比b[0]大，则b[1]=6，说明长度是2时，递增子序列的最小末尾是6，
a[2]=7,，7比b[1]大，则b[2]=7，说明长度是3时，递增子序列的最小末尾是7，
a[3]=1，找到b[0]位置，替换掉以前的5，b[0]=1，说明长度是1时，递增子序列的最小末尾数现在更新为1，这样做即使最终的最大的递增子序列不包含1，但是为了以后可能在8之后可能出现3,4，5，6,7，就可以更新长度了。
a[4]=2，找到b[1]位置，替换掉以前的6，b[1]=2，说明长度是2时，递增子序列的最小末尾数现在更新为2，
a[5]=8，比b[2]=7大，则b[3]=8，表示长度是4时，递增子序列的最小末尾数是8。
至此，a已经遍历完毕，b数组长度是4，说明最大递增子序列长度是4。
在b中查找更新的位置时，由于b已经有序，可以用二分查找法，时间复杂度是O(logN)，遍历a数组是O(N)，这样时间复杂度是O(NlogN)。
上代码：
int twosearch(vector<int>a, int x) { int l = 0; int r = a.size() - 1; int mid; while (l<=r) { mid = l + (r - l) > 1; if (x == a[mid]) return mid; else if (x>a[mid]) l = mid + 1; else r = mid - 1; } return l; } int maxup2(vector<int>a) { vector<int>b; b.push_back(a[0]); for (int i = 1; i < a.size();i++) { if (a[i]>b[b.size()-1]) b.push_back(a[i]); else { int temp = twosearch(b, a[i]); b[temp] = a[i]; } } return b.size(); } int main() { vector<int>a = { 5, 6, 7, 1, 2, 8 }; //方法三： cout << "-----------this is the third mathod's result---------" << endl; cout << maxup2(a) << endl; system("pause"); return 0; }