题意：求最长递增子序列
复杂度为O(N*N)的算法，我把找最大的放在两重for循环里居然wa了n次。。。
但是为什么呢。。。
注意dp[i]要初始化为1；
把那个找最大值的单独放在外面用一重for循环解决。
#include<cstdio>
#include<iostream>
#include<cstring>
#define INF 0xffffff
using namespace std;
int a[1010],pre[1010],dp[1010];
int main()
{
int n,i,j,maxl;
while(scanf("%d",&n)!=EOF)
{
for(i=1;i<=n;i++)
{
scanf("%d",&a[i]);
dp[i]=1;
}
maxl=-1;
for(i=2;i<=n;i++)
{
for(j=1;j<i;j++)
{
if(a[i]>a[j] && dp[i]<dp[j]+1)
dp[i]=dp[j]+1;
}
}
for(int i=1;i<=n;i++)
{
if(dp[i]>maxl)
maxl=dp[i];
}
printf("%d\n",maxl);
}
return 0;
}
//0ms
#include<cstdio>
#include<iostream>
#include<cstring>
#define INF 0xffffff
using namespace std;
int a[1010],pre[1010],dp[1010];
int main()
{
int n,i,j,maxl;
while(scanf("%d",&n)!=EOF)
{
for(i=1;i<=n;i++)
{
scanf("%d",&a[i]);
dp[i]=1;
}
for(i=1;i<=n;i++)
{
int m=0;
for(j=1;j<i;j++)
{
if(a[i]>a[j] && dp[j]>m)
m=dp[j];
}
dp[i]=m+1;
}
maxl=-1;
for(int i=1;i<=n;i++)
{
if(dp[i]>maxl)
maxl=dp[i];
}
printf("%d\n",maxl);
}
return 0;
}
//0ms
开始wa的写法：
maxl=-1;
for(i=2;i<=n;i++)
{
for(j=1;j<i;j++)
{
if(a[i]>a[j] && dp[i]<dp[j]+1)
{
dp[i]=dp[j]+1;
if(dp[i]>maxl)
maxl=dp[i];
}
}
}
printf("%d\n",maxl);