题解 | #合唱队#

1、计算出每个同学左边最多有几个人满足从左到右依次增大的序列要求 以自身为结尾，依次++循环比较. 2、计算出每个同学右边最多有几个人满足从右到左依次增大的序列要求 以自身为开头，依次--循环比较. 3、最后两个数组的值相加，再加1(自身)。判断最大值是真实的值。(其余值都不准)，可以判断出最多有多少人可以组成合唱队

#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 = 1; i < N; i++)
    {
        for(int j = 0; j < i; j++)
        {
            if(stu[i] > stu[j])
            {
                left[i] = MAX(left[i], left[j]+1);//符合条件后，应该递增。所以+1
            }
        }
    }
#if 0
    /* 打印从左到右依次增大的系列个数 */
    for(int i = 0; i < N; i++)
    {
       printf("left[%d] = [%d]\n", i, left[i]);
    }
#endif  
    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]+1);//符合条件后，应该递增。所以+1
            }
        }
    }
#if 0
    /* 打印从右到左依次增大的系列个数 */
    for(int i = 0; i < N; i++)
    {
       printf("right[%d] = [%d]\n", i, right[i]);
    }
#endif
    int max = 0;
    for(int i = 0; i < N; i++)
    {
        max = MAX(max, right[i] + left[i]+1);    //要加上本身
    }
    int min = N - max;
    printf("%d\n", min);
    return 0;
}