原题链接： 最长上升子序列
参考：
http://blog.csdn.net/shuangde800/article/details/7474903
紫书P274~275
题目大意：
给定n个整数A1,A2...An,从左到右的顺序选出尽量多的整数，组成一个上升子序列（子序列可以理解为：删除0个或多个数，其他数的顺序不变。）例如序列1,6,2,3,7,5，可以选出上升子序列·1,2,3,5，也可以选出1,6,7，但前者跟车，选出的上升子序列中相邻的元素不能相等。（紫书P274）
解题思路：
O(nlogn):（代码一）
我是从紫书上看到这道题的，所以先写按dp写的，不过看到说有O(nlogn)的算法，我就搜了一下，找到了一篇大神写得（上边有地址），写得很详细，用了一个例子把计算过程演示了一遍，很清晰。
整个过程需要两个数组：d[n]用来存储序列，B[n]用来存储：序列中长度为j的最长上升子序列的最小末尾,并且用len表示当前B内已经存储的元素个数。然后迭代d数组中的每一个元素：找到b[i]在中B[len]的最下届pos，如果当前d[i] > B[len],pos == len+1,则将d[i]存入B[++len]中。如果d[i] < B[len]，则pos<len，应将B[pos]更新为b[i]，len不变。迭代完之后，就可以求出LIS的长度。
动态规划（O(n²)）：（代码二）
由于我是看着紫书写的动态规划的代码，所以思想和紫书上是一样的：状态：用d(i)表示以i结尾的最长上升子序列的长度，则d(i)=max{0,d(j)|j<i,Aj<Ai}+1，最终答案是max{d[i]}.
使用LCS间接计算（O(n²))：（代码三）
思路很简单就是使用另一个数组来存储序列，然后进行排序，然后求原序列和排序后序列的LCS(最长公共子序列)，就可以得到LIS。状态：使用d(i,j)来保存A1,A2...Ai和B1,B2,...Bj的LIS长度，状态转移方程：如果Ai==Bj，则d(i,j)=d(i-1,j-1)+1。否则d(i,j) = max{d(i-1,j),d(i,j-1)}。最终d[n][n]就是LIS和LCS的长度。
遇到问题：
在写第三中方法的时候是用了memcpy函数，memcpy(a,b,sizeof(a))可以得出结果，memcpy(a,b,n+1)就不对，只能复制一部分，很迷。。
代码：
代码一：
#include<iostream>
#include<algorithm>
using namespace std;
const int MAXN = 100000 + 10;
int n, list[MAXN], d[MAXN];//d(i):长度为i的最长上升子序列的最小末尾
int main()
{
while (cin >> n) {
for (int i = 1; i <= n; i++) cin >> list[i];
list[0] = -1; d[0] = -1;
int len = 0;
for (int i = 1; i <= n; i++) {
if (list[i] != d[len]) {
int pos = lower_bound(d + 1, d + len + 1, list[i]) - d;
d[pos] = list[i];
if (list[i] > d[len]) len++;
}
}
cout << len << endl;
}
return 0;
}
代码二（TLE）：
#include<iostream>
#include<algorithm>
using namespace std;
const int MAXN = 100000 + 10;
int n, list[MAXN], d[MAXN];//d(i):以i结尾的最长上升子序列的长度
//转移方程d(i) = max{0,d(j)|i >j,Ai > Aj}+1
int dp()
{
int max_len = 0;
for (int i = 1; i <= n; i++) {
for (int j = 0; j < i; j++) {
if (list[j + 1] > list[j])
d[i] = max(0, d[j]) + 1;
}
max_len = max(max_len, d[i]);
}
return max_len;
}
int main()
{
while (cin >> n) {
for (int i = 1; i <= n; i++) cin >> list[i];
list[0] = -1; d[0] = 0;
cout << dp() << endl;
}
return 0;
}
代码三(MLE)：
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int MAXN = 10000 + 10;
int n, list[MAXN],srt_list[MAXN], d[MAXN][MAXN];
int main()
{
while (cin >> n) {
for (int i = 1; i <= n; i++) { cin >> list[i]; srt_list[i] = list[i]; }
sort(srt_list, srt_list + n + 1);
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
if (list[i] == srt_list[j]) {
d[i][j] = d[i - 1][j - 1] + 1;
}
else {
d[i][j] = max(d[i - 1][j], d[i][j - 1]);
}
}
}
cout << d[n][n] << endl;
}
return 0;
}
