1. 动态规划:时间复杂度O(n^2) 
    #include <stdio.h>
#include <string.h>

int main(){
    int N;scanf("%d",&N);
    int a[N];int max;
    for(int i=0;i<N;i++){
        scanf("%d",&a[i]);
    }
    //逆序遍历，以当前元素为基准，记录其右边的最大严格递减序列的元素个数
    int dp_r[N];memset(dp_r,0,sizeof(dp_r));
    for(int i=N-2;i>-1;i--){
        max=-1;
        for(int j=i+1;j<N;j++){
            if(a[i]>a[j] && dp_r[j]>max){
                max=dp_r[j];
                dp_r[i]=dp_r[j]+1;
            }
        }
    }
    //顺序遍历，以当前元素为基准，记录其左边的最大严格递增序列的元素个数
    int dp_l[N];memset(dp_l,0,sizeof(dp_l));
    for(int i=1;i<N;i++){
        max=-1;
        for(int j=i-1;j>-1;j--){
            if(a[i]>a[j] && dp_l[j]>max){
                max=dp_l[j];
                dp_l[i]=dp_l[j]+1;
            }
        }
    }
    //遍历整个数组，计算当前元素dp_r[i]+dp_l[i]的大小，计算最大值
    for(int i=0;i<N;i++){
        if(dp_r[i]+dp_l[i]>max){
            max=dp_r[i]+dp_l[i];
        }
    }
    printf("%d",N-max-1);
}
  2. 建立辅助数组，维持辅助数组元素有序排列，用二分查找找到原数组元素在该辅助数组中该插入的位置，该位置即为动态规划中dp[i]的值，时间复杂度O(nlogn) 
    #include <stdio.h>
#include <string.h>

int search(int* a,int key,int high){//二分查找
    int low=0,mid;
    while(low<=high){
        mid=(low+high)/2;
        if(a[mid]==key){
            return mid;
        }
        else if(a[mid]>key){
            high=mid-1;
        }
        else{
            low=mid+1;
        }
    }
    if(a[mid]>key){
        return mid;
    }
    else{
        return mid+1;
    }
}

int main(){
    int N;scanf("%d",&N);
    int a[N];int b[N];memset(b,0,sizeof(b));//辅助数组
    for(int i=0;i<N;i++){
        scanf("%d",&a[i]);
    }
    int max=0;int p;
    //顺序遍历，以当前元素为基准，记录其左边的最大严格递增序列的元素个数
    int dp_l[N];dp_l[0]=0;
    b[max]=b[0]=a[0];
    for(int i=1;i<N;i++){
        if(a[i]<=b[0]){//原数组元素值超过辅助数组下界就替换
            dp_l[i]=0;
            b[0]=a[i];
        }
        else if(a[i]>b[max]){//原数组元素值超过辅助数组上界，将其插入后形成新的上界
            dp_l[i]=++max;
            b[max]=a[i];
        }
        else{//原数组元素值在中间就在辅助数组中查找刚好大于它的数并替换
            p=search(b,a[i],max);
            dp_l[i]=p;
            b[p]=a[i];
        }
    }
    max=0;
    //逆序遍历，以当前元素为基准，记录其右边的最大严格递减序列的元素个数
    int dp_r[N];dp_r[N-1]=0;memset(b,0,sizeof(b));
    b[max]=b[0]=a[N-1];
    for(int i=N-2;i>-1;i--){
        if(a[i]<=b[0]){//原数组元素值超过辅助数组下界就替换
            dp_r[i]=0;
            b[0]=a[i];
        }
        else if(a[i]>b[max]){//原数组元素值超过辅助数组上界，将其插入后形成新的上界
            dp_r[i]=++max;
            b[max]=a[i];
        }
        else{//原数组元素值在中间就在辅助数组中查找刚好大于它的数并替换
            p=search(b,a[i],max);
            dp_r[i]=p;
            b[p]=a[i];
        }
    }    
    //遍历整个数组，计算当前元素dp_r[i]+dp_l[i]的大小，计算最大值
    for(int i=0;i<N;i++){
        if(dp_r[i]+dp_l[i]>max){
            max=dp_r[i]+dp_l[i];
        }
    }
    printf("%d",N-max-1);
}