POJ2533——DP（LCS+LDS）——Longest Ordered Subsequence

#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int MAX = 11000;
int a[MAX],b[MAX];
int main()
{
    int n;
    int l,r,mid;
    scanf("%d",&n);
    for(int i = 1; i <= n ;i++)
        scanf("%d",&a[i]);
        // LCS
    b[1] = a[1];
    int k,i;
    for(i = 2, k = 1; i <= n ;i++){
            if(a[i] > b[k]) b[++k] = a[i];
           else {
            l = 1; r = k;
              while(l<=r){
                   mid = (l + r) >> 1;
                   if(b[mid] < a[i]) l = mid + 1;
                   else if(b[mid] > a[i]) r = mid - 1;
                   else break;
              }
              b[l] =a[i];
           }
    }
    int temp1 = k;
    // LDS
    memset(b,0,sizeof(b));
    b[1] = a[1];
    for(i = 2, k = 1; i <= n ;i++){
           if(a[i] < b[i]) b[++k] = a[i];
          else {
              l = 1; r = k;
             while(l <= r){
              mid = (l + r) >> 1;
             if(b[mid] > a[i]) l = mid + 1;
             else if(b[mid] < a[i]) r = mid -1;
             else break;
             }
             b[l] = a[i];
          }
    }
    int temp2 = k;
    printf("%d",max(temp1,temp2));
    return 0;
}