hdu1257(最长上升子序列)

题目链接：kuanbin带你飞基础dp专题:hdu1257
这是一道经典的LIS题目。一句话可以概括这道题目的变形：最长上身子序列的长度等于不下降子序列的个数。然后用dp做的时间复杂度是O(n),可以用二分优化，时间复杂度为O(nlogn)。
ac代码:

#include <bits/stdc++.h>
using namespace std;
int a[1000000], dp[1000000];
int main(void)
{
    int N;
    while(scanf("%d", &N)!=EOF)
    {
        memset(dp, 0, sizeof(dp));
        dp[0]=1;
        for(int i=0; i<N; i++)
        scanf("%d", &a[i]);
        for(int i=0; i<N; i++)
        {
            for(int j=0; j<i; j++)
            {
                if(a[i]>a[j])
                dp[i]=max(dp[i], dp[j]+1);
            }
            if(dp[i]==0)dp[i]=1;
        }
        int M=-1;
        for(int i=0; i<N; i++)M=max(M, dp[i]);
        printf("%d\n", M);
    }
    return 0;
}