最长不递减子序列

 1 //DP
 2 int LDNS(int a[], int n)
 3 {
 4     int DP[n];
 5     int Cnt=-1;
 6     memset(DP, 0, sizeof(DP));
 7     for(int i=0; i<n; i++ )
 8     {
 9         for(int j=0; j<i; j++ )
10         {
11             if( a[i]>=a[j] )//和最长子序列的区别之处
12             {
13                 DP[i]=max(DP[i], DP[j]+1);
14                 Cnt=max(Cnt, DP[i]);
15             }
16         }
17     }
18     return Cnt+1;
19 }

 1 1 int LDNS(int a[], int n)
 2  2 {
 3  3     int Cnt=0;
 4  4     int Array[n+1];
 5  5     Array[0]=a[0];
 6  6     for(int i=1; i<n; i++ )
 7  7     {
 8  8         if( a[i]>=Array[Cnt] )
 9  9             Array[++Cnt]=a[i];
10 10             else
11 11             {
12 12                 int Index=upper_bound(Array, Array+Cnt+1, a[i])-Array;
13 13                 Array[Index]=a[i];
14 14             }
15 15     }
16 16     return Cnt+1;
17 17 }