合唱队行

最长上升子序列的变式。
先从左往右求一遍最长上升子序列(dpl)，再从右往左求一遍(dpr)。
结果遍历一遍从左和从右的dp值和(dpr[i]+dpl[i])，找出和为最大的-1即为最大正常先递增再递减的子序列长度，
-》n-长度即为需要出列的最少同学数。

AC代码如下

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int Max = 1e5 + 5;
int lst[Max];
int dpl[Max],dpr[Max];

int main()
{
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        scanf("%d", &lst[i]);
    }
    dpl[1] = 1;
    for (int i = 2; i <= n; i++)
    {
        int m=0;
        for (int j = 1; j < i; j++)
        {
            if (lst[i] > lst[j] && dpl[j] > m) m = dpl[j];
        }
        dpl[i] = m + 1;
    }
    dpr[n] = 1;
    for (int i = n-1; i >= 1; i--)
    {
        int m = 0;
        for (int j = n; j >= i; j--)
        {
            if (lst[i] > lst[j] && dpr[j] > m) m = dpr[j];
        }
        dpr[i] = m + 1;
    }
    int sum=-99;
    for (int i = 1; i <= n; i++) sum = max(sum, dpl[i] + dpr[i] - 1);
    cout << n - sum << endl;
}