在O(n^2)内求n个数的最长单调递增子数列。思路:利用动态规划的思路求解。c[i]存放到第i个数时，最长递增子数列的长度。b[i]存放比第i个数小的第j个数的下标(j<=i)。
代码如下：
//最长递增子数列O(n^2)时间复杂度内完成。
//采用动态规划方法
#include<iostream>
using namespace std;
int LongestUpSeries(int *n,int length,int *c,int *b)
{
int i,j;
//数组元素从下标0开始，第一个元素的最长递增数列长度为1
c[0]=1;
//设置标志位，b[i]存放前一个数字的下标，如果该元素为最长递增子数列
//的第一个元素，则b[i]指向当前位置
b[0]=0;
if(length==0)
{
return 0;
}
for(i=1;i<=length;i++)
{
for(j=0;j<=i;j++)
{
if(i==j)
break;
if(n[i]>n[j])
{
if(c[i]<c[j]+1)
{
//b[i]记录比第i个数小的第j个数的下标
c[i]=c[j]+1;
b[i]=j;
}
}
else
{
//如果第i个数小于等于第j个数，则c[i]保持原来数字或为1
if(c[i]==0)
c[i]=1;
b[i]=i;
}
}
}
if(n[b[i-1]]<n[length])
{
b[i]=length;
}
else
b[i]=b[i-1];
return c[length];
}
void PrintAnswer(int *n,int *b,int length)
{
if(length!=b[length])
{
PrintAnswer(n,b,b[length]);
cout<<n[b[length]]<<" ";
}
}
int main()
{
int n[11]={0,1,3,5,1,4,6,7,0,8,9};
int c[11]={0};
int b[12]={0};
cout<<LongestUpSeries(n,10,c,b)<<endl;
PrintAnswer(n,b,11);
return 0;
}