poj 2533 Longest Ordered Subsequence （LIS）

题意：求最长递增子序列

复杂度为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

        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);

poj 2533 Longest Ordered Subsequence （LIS）

原文：http://blog.csdn.net/u012841845/article/details/18445909