最长递增子序列
Time Limit: 1000 MS Memory Limit: 32768 K
Total Submit: 377(132 users) Total Accepted: 170(122 users) Rating: Special Judge: No
Description
给出一个数字序列求其最长的递增子序列例如序列(1,7,3,5,9,4,8).
(1,7)和(3,4,8)是其递增子序列但其最长的递增子序列是(1,3,5,8)。
Input
本题有多组测试数据，对于每组测试数据第一行是一个整数n(n<=100)代表序列长度。
第二行是n个整数。
Output
最长递增子序列长度
Sample Input
7
1 7 3 5 9 4 8
Sample Output
4
最长子序列系列，对数列进行遍历，找出当前遍历数字之前的数列中，符合递增条件的(>=)最长长度，并转移继承，符合条件的数字记录下来它的存储长度，并在传递到遍历的数字时+1（遍历数字本身）存储起来
#include<stdio.h>///超棒！最长递增子序列get√
#include<string.h>///实际上就是将每个数和前面的前面的最大值比较，选取最大值加上并赋值给正在遍历的数
#include<algorithm>
using namespace std;
int main()
{
int i,j,a[1080],dp[1080],n;///两个数组，dp数组和输入数组
while(scanf("%d",&n)!=EOF)
{
for(i=0;i<n;i++)
{
scanf("%d",&a[i]);
}
memset(dp,0,sizeof(dp));
int flag;
int maxn=1;
dp[0]=1;///初始第一个遍历的数为长度1
for(i=1;i<n;i++)///开始动态规划
{
flag=dp[i];///记录此时遍历数字的长度，一般被初始化为0
for(j=0;j<i;j++)///检查前面的dp数组中存储的最长长度
{
if(a[i]>a[j]&&dp[j]>flag)///若满足递增条件，且找到了最大长度
{
flag=dp[j];///记录长度
}///如果符合递增序列的条件，那么就将其长度记录，到flag，便于存至第i位作为最长长度
}
dp[i]=flag+1;///若遍历过了的i，则将最长长度+1，表示为i的长度
maxn=max(maxn,dp[i]);///还是直接遍历取最大值吧
}///作为最长长度，从flag中+1（i本身）记录到第i个数中
// for(i=0;i<=n;i++)
// {
// printf("%d
",dp[i]);
// }
// sort(dp,dp+n);///这里找dp出来的长度最大值，有点小题大做了，但是为了省事
printf("%d
",maxn);
}
return 0;
}