最长不递减子序列

定义：在最长上升序列的基础上，允许相同的若干元素出现在子序列中

DP做法：

 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         for(int j=0; j<i; j++ ){
 9             if( a[i]>=a[j] )//和最长子序列的区别之处
10             {
11                 DP[i]=max(DP[i], DP[j]+1);
12                 Cnt=max(Cnt, DP[i]);
13             }
14         }
15     }
16     return Cnt+1;
17 }

贪心＋二分法：

注意：把在“最长子序列”里的lower_bound改为upper_bound，原因是lower_bound返回的是第一个大于等于a[i]的地址，在允许子序列有重复元素时可能会造成相同元素覆盖，使得求得的长度变短

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