题解 | #合唱队#

思路：本质就是求最长上升/下降子序列的问题
1、先找到每一个位置i左侧的最长上升子序列长度left[i]：每一个位置左侧最长子序列长度等于其左侧比它小的所有位置的最长子序列长度中的最大值+1
2、再找到每一个位置i右侧的最长下降子序列长度right[i]：每一个位置右侧最长子序列长度等于其右侧比它小的所有位置的最长子序列长度中的最大值+1
3、然后求出所有位置的最长序列长度=左侧最长子序列长度+右侧最长子序列长度-1（因为该位置被算了两次，所以减1）
4、然后用数目减去最长序列长度就是答案

#include <stdio.h>

#define MAX(a, b) (a > b)?a:b
int main()
{
    int N = 0;
    scanf("%d", &N);
    int stu[N];    //保存学生身高
    int left[N];    //保存左边满足条件的同学数(包含自己)
    int right[N];   //保存右边满足条件的同学数
    memset(stu, 0, N*sizeof(int));
    memset(left, 0, N*sizeof(int));
    memset(right, 0, N*sizeof(int));

    for(int i = 0; i < N; i++)
    {
        scanf("%d", &stu[i]);
    }

    //左侧最长上升子序列
    for(int i = 0; i < N; i++)
    {
        for(int j = 0; j < i; j++)
        {
            if(stu[i] > stu[j])
            {
                left[i] = MAX(left[i], left[j]);
            }
        }
        left[i] = left[i] + 1;
    }
     //右侧最长下降子序列
    for(int i = N-1; i >= 0; i--)
    {
        for(int j = N-1; j > i; j--)
        {
            if(stu[i] > stu[j])
            {
                right[i] = MAX(right[i], right[j]);
            }
        }
        right[i] = right[i] + 1;
    }

    int max = 0;    //最多需要去掉多少人
    for(int i = 0; i < N; i++)
    {
        if(max < left[i]+right[i]-1)
        {
            max = left[i]+right[i]-1;    
        }
    }
    int min = N - max;    //最少去掉的人数 = 全部人数 - 最多去掉的人数
    printf("%d\n", min);
    return 0;
}