dp--最长上升子序列LIS

1759:最长上升子序列

描述

一个数的序列b，当b < b < ... < b的时候，我们称这个序列是上升的。对于给定的一个序列(a, a, ..., a)，我们可以得到一些上升的子序列(a, a, ..., a)，这里1 <= i < i < ... < i <= N。比如，对于序列(1, 7, 3, 5, 9, 4, 8)，有它的一些上升子序列，如(1, 7), (3, 4, 8)等等。这些子序列中最长的长度是4，比如子序列(1, 3, 5, 8).

n方作法：

dp[i]表示以i为结尾，所形成的最长上升自序列

每次当[i]>a[j]的时候，即说明j可以放在a的后面

dp[i] = max(dp[j]+1,dp[i])

     for (int i = ;i <= n;i++)

         for (int j = ;j <= i-;j++)

         {

             if (a[j]<a[i])

             dp[i] = max(dp[j]+,dp[i]);

         }

完整代码：

 #include <cstdio>

 #include <iostream>

 using namespace std;

 int dp[];

 int main()

 {

     int n;

     int a[];

     scanf ("%d",&n);

     int dp[];

     for (int i = ;i <= n;i++)

     {

         scanf ("%d",&a[i]);

         dp[i] = ;

     }

     for (int i = ;i <= n;i++)

         for (int j = ;j <= i-;j++)

         {

             if (a[j]<a[i])

             dp[i] = max(dp[j]+,dp[i]);

         }

     int ans=;

     for (int i = ;i <= n;i++)

         ans=max(dp[i],ans);

     cout<<ans;

     return ;

 }

nlogn作法：

     for (int i = ;i <= n;i++)

     {

         if (c[num]<a[i])

             c[++num]=a[i];

         else

         {

             int pos=lower_bound(c+,c+num+,a[i])-c;

             c[pos]=a[i];

         }

     }

     printf ("%d",num);