【十二题解】 | #合唱队#

最长子序列问题，但是有几个细节需要注意一下

1、dp数组的含义分别是在第i个时，连续增长的最大个数

2、这里两个dp数组，一个是正序的增长子序列，一个是逆序的增长子序列（注意不能是正序的递减子序列，否则状态推的方向完全就反了）

#include<stdio.h>

int f_max(int a, int b){

return a>b?a:b;

}

int main(){

int number;
int height[3000]={0};
while(scanf("%d", &number) != EOF){
    for(int i = 0; i < number; i++){
        scanf("%d",&height[i]);
    }
    int dp_up[3000]={0};
    for(int i=0; i<number; i++)dp_up[i]=1;
    int dp_down[3000]={0};
    for(int i=0; i<number; i++)dp_down[i]=1;
    for(int i=1; i<number; i++){
        for(int j=0; j<i; j++){
            if(height[i]>height[j])dp_up[i]=f_max(dp_up[i], dp_up[j]+1);
            }
        }
    
    for(int i=number-2; i>=0; i--){
        for(int j=number-1; j>i; j--){
            if(height[i]>height[j])dp_down[i]=f_max(dp_down[i], dp_down[j]+1);
            }
        }
    int max = 0;
    for(int i=0; i<number; i++)max=f_max(max, dp_up[i]+dp_down[i]-1);
    printf("%d\n", number-max);
}
return 0;

}