合唱队形

先看题目：https://ac.nowcoder.com/acm/problem/16664
题目描述：
n个人为了排成最长的合唱队形需要多少人出列？(合唱队形是指T1 < T2 < ... < Ti > Ti+1 > ... > Tn)
解题思路：
先从前往后通过求最长上升子序列，得到以每个点为结束的最长上升子序列
再对序列从后往前求一遍最长下降子序列，得到以每个点为开始的最长下降子序列
然后遍历一遍序列，取个max
代码：

#include<bits/stdc++.h>
using namespace std;
int a[110];
int dp1[110];
int dp2[110];
int main()
{
    int n;
    scanf("%d",&n);
    for(int i = 1; i <= n; i++){
        scanf("%d",&a[i]);
    }
    for(int i = 1; i <= n; i++) {
        dp1[i] = 1;
        dp2[i] = 1;
    }
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j < i; j++) {
            if(a[j] < a[i]) {
                dp1[i] = max(dp1[i], dp1[j]+1);
            }
        }
    }
    for(int i = n; i >= 1; i--) {
        for(int j = n; j > i; j--) {
            if(a[j] < a[i]) {
                dp2[i] = max(dp2[i], dp2[j]+1);
            }
        }
    }
    int ans = 0;
    for(int i = 1; i <= n; i++) {
        ans = max(ans, dp1[i]+dp2[i]-1);
    }
    printf("%d\n",n-ans);
}