原题；
题目描述
一个数的序列bi，当b
1
< b
2
< ... < b
S
的时候，我们称这个序列是上升的。对于给定的一个序列(a
1
, a
2
, ..., a
N
)，我们可以得到一些上升的子序列(a
i1
, a
i2
, ..., a
iK
)，这里1<= i
1
< i
2
< ... < i
K
<= N。比如，对于序列(1, 7, 3, 5, 9, 4, 8)，有它的一些上升子序列，如(1, 7), (3, 4, 8)等等。这些子序列中最长的长度是4，比如子序列(1, 3, 5, 8)。
你的任务，就是对于给定的序列，求出最长上升子序列的长度。
你的任务，就是对于给定的序列，求出最长上升子序列的长度。
输入
输入的第一行是序列的长度N (1 <= N <= 1000)。第二行给出序列中的N个整数，这些整数的取值范围都在0到10000。
输出
最长上升子序列的长度。
示例输入
7
1 7 3 5 9 4 8
示例输出
4
分析：
dp第二弹~~~~~
源码1——dp
#include<iostream>
#include<string.h>
using namespace std;
int num[1024];
int a[1024];
int p(int i)
{
if(i==1)
return a[1];
else
{
int max=0;
for(int j=1; j<i; j++)
{
if (a[j]==0)
a[j] = p(j);
if((a[j]>max)&&(num[i]>num[j]))
max=a[j];
}
a[i] = max+1;
}
return a[i];
}
int main()
{
int n;
cin>>n;
for(int i=1; i<=n; i++)
{
cin>>num[i];
}
memset(a,0,sizeof(a));
a[1]=1;
p(n);
int max=0;
for (int i=1; i<=n; i++)
{
if (a[i]>max)
max=a[i];
}
cout<<max<<endl;
return 0;
}
源码2：又称作LIS算法
#include<stdio.h>
int z[1007],dp[1007];
int main()
{
int n,i,j;
scanf("%d",&n);
for(i=1; i<=n; i++)
{
scanf("%d",&z[i]);
}
dp[1]=z[1];
int left,right,lenth=1;
for(j=2; j<=n; j++)
{
left=1;
right=lenth;
while(left<=right)
{
int mid=(left+right)/2;
if(dp[mid]<z[j])
{
left=mid+1;
}
else right=mid-1;
}
dp[left]=z[j];
if(left>lenth)
lenth++;
}
printf("%d\n",lenth);
return 0;
}
