问题：
设计一个O(n^2)时间的算法，找出由n个数组成的序列的最长单调递增子序列。
方法一：最长公共子序列，动态规划。
思路：1：将数组a复制到b；
2：对b排序；
3：对数组b去重(注意去重是必要的，因为要求单调递增)，这里利用hash表去重。
4：求a， b数组的最长公共子序列。
求最长公共子序列方法见 javascript:void(0)
代码：
#include <bits/stdc++.h>
using namespace std;
int a[1024]; //原数组
int b[1024]; //排序后数组
int ans[1024][1024]; //记录 c[i][j] 的值是有哪个子问题得到
int c[1024][1024]; //最长子序列长度
int n; //数组长度
int m; //去重后的长度
void LCS(int i, int j)
{
if(i == 0 || j == 0)
return;
else if(ans[i][j] == 1)
{
LCS(i - 1, j - 1);
cout << a[i] << " ";
}
else if(ans[i][j] == 2)
{
LCS(i - 1, j);
}
else
{
LCS(i, j - 1);
}
}
void LCSLegth()
{
memset(ans, 0, sizeof(ans));
memset(c, 0, sizeof(c));
for(int i = 1; i <= n; ++i)
{
for(int j = 1; j <= m; ++j)
{
if(a[i] == b[j])
{
c[i][j] = c[i - 1][j - 1] + 1;
ans[i][j] = 1;
}
else if(c[i - 1][j] > c[i][j - 1])
{
c[i][j] = c[i - 1][j];
ans[i][j] = 2;
}
else
{
c[i][j] = c[i][j - 1];
ans[i][j] = 3;
}
}
}
}
void HashTable()
{
int max_ = b[n];
m = 0;
int *p = new int(max_);
memset(p, 0, sizeof(p));
for(int i = 1; i <= n; ++i)
{
p[b[i]] = 1;
}
memset(b, 0, sizeof(b));
for(int i = 0; i <= max_; ++i)
{
if(p[i] == 1)
b[++m] = i;
}
delete []p;
p = NULL;
}
void solve()
{
sort(b + 1, b + n);
HashTable(); //去重
// for(int i = 1; i <= m; ++i)
// cout << b[i] << " ";
// cout << endl;
LCSLegth();
LCS(n, m);
}
void inPut()
{
scanf("%d", &n);
for(int i = 1; i <= n; ++i)
{
scanf("%d", &a[i]);
b[i] = a[i];
}
}
int main()
{
inPut();
solve();
}方法二：动态规划
思路：F[i]的含义为：在“可取元素为前i”且“取第i个元素”时最长递增序列的长度。
则可得递归关系为： F[i] = max(F[k]) + 1, 1 <= k <= i - 1 && a[i] > a[k]
代码：
#include <bits/stdc++.h>
using namespace std;
int a[1024]; //原数组
int F[1024]; //在i处的长度
int n; //数组长度
int max_ = 0; // 最长长度
void solve()
{
for(int i = 1; i <= n; ++i)
F[i] = 1;
for(int i = 1; i <= n; ++i)
{
for(int j = 1; j < i; ++j)
{
if(a[i] > a[j] && F[i] < F[j] + 1)
F[i] = F[j] + 1;
}
}
for(int i = 1; i <= n; ++i)
if(F[i] > max_)
max_ = F[i];
}
void inPut()
{
scanf("%d", &n);
for(int i = 1; i <= n; ++i)
{
scanf("%d", &a[i]);
}
}
int main()
{
inPut();
solve();
}
方法三：Nlog（N)
假设存在一个序列d[1..9] = 2 1 5 3 6 4 8 9 7，可以看出来它的LIS长度为5。
下面一步一步试着找出它。
我们定义一个序列B，然后令 i = 1 to 9 逐个考察这个序列。
此外，我们用一个变量Len来记录现在最长算到多少了
首先，把d[1]有序地放到B里，令B[1] = 2，就是说当只有1一个数字2的时候，长度为1的LIS的最小末尾是2。这时Len=1
然后，把d[2]有序地放到B里，令B[1] = 1，就是说长度为1的LIS的最小末尾是1，d[1]=2已经没用了，很容易理解吧。这时Len=1
接着，d[3] = 5，d[3]>B[1]，所以令B[1+1]=B[2]=d[3]=5，就是说长度为2的LIS的最小末尾是5，很容易理解吧。这时候B[1..2] = 1, 5，Len＝2
再来，d[4] = 3，它正好加在1,5之间，放在1的位置显然不合适，因为1小于3，长度为1的LIS最小末尾应该是1，这样很容易推知，长度为2的LIS最小末尾是3，于是可以把5淘汰掉，这时候B[1..2] = 1, 3，Len = 2
继续，d[5] = 6，它在3后面，因为B[2] = 3, 而6在3后面，于是很容易可以推知B[3] = 6, 这时B[1..3] = 1, 3, 6，还是很容易理解吧？ Len = 3 了噢。
第6个, d[6] = 4，你看它在3和6之间，于是我们就可以把6替换掉，得到B[3] = 4。B[1..3] = 1, 3, 4， Len继续等于3
第7个, d[7] = 8，它很大，比4大，嗯。于是B[4] = 8。Len变成4了
第8个, d[8] = 9，得到B[5] = 9，嗯。Len继续增大，到5了。
最后一个, d[9] = 7，它在B[3] = 4和B[4] = 8之间，所以我们知道最新的B[4] =7，B[1..5] = 1, 3, 4, 7, 9，Len = 5。
于是我们知道了LIS的长度为5。
!!!!! 注意。这个1,3,4,7,9不是LIS，它只是存储的对应长度LIS的最小末尾。有了这个末尾，我们就可以一个一个地插入数据。虽然最后一个d[9] = 7更新进去对于这组数据没有什么意义，但是如果后面再出现两个数字 8 和 9，那么就可以把8更新到d[5], 9更新到d[6]，得出LIS的长度为6。
然后应该发现一件事情了：在B中插入数据是有序的，而且是进行替换而不需要挪动——也就是说，我们可以使用二分查找，将每一个数字的插入时间优化到O(logN)~~~~~于是算法的时间复杂度就降低到了O(NlogN)～！
代码如下:
//在非递减序列 arr[s..e]（闭区间）上二分查找第一个大于等于key的位置，如果都小于key，就返回e+1
int upper_bound(int arr[], int s, int e, int key)
{
int mid;
if (arr[e] <= key)
return e + 1;
while (s < e)
{
mid = s + (e - s) / 2;
if (arr[mid] <= key)
s = mid + 1;
else
e = mid;
}
return s;
}
int LIS(int d[], int n)
{
int i = 0, len = 1, *end = (int *)alloca(sizeof(int) * (n + 1));
end[1] = d[0]; //初始化：长度为1的LIS末尾为d[0]
for (i = 1; i < n; i++)
{
int pos = upper_bound(end, 1, len, d[i]); //找到插入位置
end[pos] = d[i];
if (len < pos) //按需要更新LIS长度
len = pos;
}
return len;
}