算法导论15.4-5 请给出一个O(n^2)时间的算法，使之能找出一个n个数的序列中最长的单调递增子序列。
这个题目是在动态规划部分，此处显然是要用到动态规划。
我们知道可以使用动态规划思想的问题的的两个重要的特征是具有最优子结构和重叠子问题。下面就来分析一下这个问题：
对于一个n个元素的序列nums，设其最长单调递增子序列为Sm(n)（m为递增子序列的长度），则对于Sm存在两种情况：
1、如果nums[n]比Sm-1的最后一个元素大，则Sm由Sm-1加nums[n]组成
2、如果nums[n]小于等于Sm-1的最后一个元素，则Sm即为Sm-1
但是这样考虑有问题，因为如果Sm-1的序列有多个，我们则应该每一个都与nums[n]考察，如果nums[n]比所有Sm-1的尾元素都小或相等，而Sm-2的序列中又存在尾元素小于nums[n]的序列，则我们应该如何选择，Sm应该是多少？ Sm-1+nums[n]、Sm-1、Sm-2+nums[n]
所以之前的分析是有问题的，在长度相同的情况下，我们优先选择包含nums[n]的序列作为Sm(n)，因为每一个新加入的元素都可能改变不同长度的递增子序列，因此我们需要维护每一个递增子序列以获取最优。
这里的最优子结构就是n个元素的最长递增子序列是从前n-1个元素结尾的递增子序列中的一个或者再加上nums[n]，这里面自然存在很多重叠子问题。
代码如下：
/************************************************************************/
/* 算法导论15.4-5
* 找出n个数的序列中最长的单调递增子序列
* 利用动态规划思想，时间复杂度为O(n^2)*/
/************************************************************************/
#include<iostream>
using namespace std;
void printSequence(int *b,int* nums,int last);
int main()
{
int n=8;
int nums[9]={0,1,7,8,9,2,3,4,5};
//b存储当前元素所在递增子序列中当前元素的前一个元素序号
//c存储以当前元素结尾的递增子序列长度
//last存储当前元素为止的序列中最长递增子序列的最后一个元素的序号
//maxLen存储当前最长递增子序列的长度
int b[9]={0},c[9]={0},last[9]={0},maxLen=0;
c[1]=1,last[1]=1;
for (int i=1;i<=n;i++)
{
for (int j=1;j<i;j++)
{
if(nums[j]<nums[i] && c[j]+1>c[i])
{
c[i]=c[j]+1;
b[i]=j;
last[i]=i;
maxLen=c[i];
}else if(c[j]>c[i]){
maxLen=c[j];
last[i]=last[j];
}
}
}
cout<<"原序列长度为"<<n<<"，如下："<<endl;
for (int i=1;i<=n;i++)
{
cout<<nums[i]<<" ";
}
cout<<endl<<"最长递增子序列长度为"<<maxLen<<"，如下："<<endl;
printSequence(b,nums,last[n]);
cout<<endl;
return 0;
}
void printSequence(int *b,int* nums,int last)
{
if(b[last]>0)
printSequence(b,nums,b[last]);
cout<<nums[last]<<" ";
}
以上程序的时间复杂度是O(n^2)，共有n个子问题，每个子问题有n个选择。
15.4-6又要求用O(nlgn)的时间复杂度来找出最长递增子序列，具体的算法思想可以参考：
http://blog.csdn.net/wdq347/article/details/8978394
下面我直接上代码
/************************************************************************/
/* 算法导论15.4-6
* 找出n个数的序列中最长的单调递增子序列
* 时间复杂度为O(nlgn)*/
/************************************************************************/
#include<iostream>
#include<vector>
using namespace std;
void printSequence(int *b,int* nums,int last);
int main()
{
int nums[]={1,7,8,9,2,3,4,5};
//数组b存储在递增子序列中当前元素的前一个元素序号
int n = sizeof(nums) / sizeof(int);
int *b=new int[n];
//vector容器last中存储各不同长度的递增子序列(同一长度的子序列，只考虑尾元素最小的序列)
// 中最后一个元素的序号
vector<int> last;
last.push_back(0);
b[0]=0;
for (int i=1;i<n;i++)
{
int low=0,high=last.size()-1;
int middle=(low+high)/2;
int pos;
if(nums[i]>nums[last[high]])
{//如果当前元素比last中所有元素都大则最长递增子序列的长度加一，其尾元素为当前元素nums[i]
last.push_back(i);
b[i]=last[high];
}else{//否则使用二分法在last中查找到大于等于当前元素nums[i]的最小元素
while(low<high)
{
middle=(high+low)/2;
if(nums[i]>nums[last[middle]])
low=middle+1;
else
high=middle-1;
}
//更新last中的元素值
if(nums[i]>nums[last[low]])
pos=low+1;
else
pos=low;
last[pos]=i;
b[i]=last[pos-1<0 ? 0 : pos-1];
}
}
cout<<"原序列长度为"<<n<<"，如下："<<endl;
for (int i=0;i<n;i++)
{
cout<<nums[i]<<" ";
}
int len=last.size();
cout<<endl<<"最长递增子序列长度为"<<len<<"，如下："<<endl;
printSequence(b,nums,last[len-1]);
cout<<endl;
delete[] b;
return 0;
}
void printSequence(int *b,int* nums,int last)
{
if(b[last]!=last)
printSequence(b,nums,b[last]);
cout<<nums[last]<<" ";
}