我把两个dp数组求出来了，根据题解，之后是取1~n为中间那个i，如何开始遍历最大

根据这个思想，我写了第一份ac代码

#include <stdio.h>
#include <stdlib.h>
int num[105],flag[105],flag2[105];
int MAX(int l,int r,int *num)	//这段程序没有用上
{
    int max=l;
    for(int i=l+1;i<=r;i++)
    {
        if(num[i]>num[max]) max=i;
    }
    return max;
}

int main()
{
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&num[i]);
        flag[i]=flag2[i]=1;
    }
    for(int i=2;i<=n;i++) //dp1
    {
        for(int k=1;k<i;k++)
            if(num[i]>num[k] && flag[k]+1>flag[i])
                flag[i]=flag[k]+1;
    }
    for(int i=n-1;i>=1;i--) //dp2
    {
        for(int k=n;k>i;k--)
            if(num[i]>num[k] && flag2[k]+1>flag2[i])
                flag2[i]=flag2[k]+1;
    }
    int max=0;
    for(int i=0;i<=n;i++)	//max
    {
        if(flag[i]+flag2[i]-1>max)  max=flag[i]+flag2[i]-1;
    }
    printf("%d\n",n-max);
    return 0;
}

但是我觉得最后关于max的讨论不对，不应该是在0~i和i~n两段分别取最长升子序列和最长降子序列吗，那个“最长”并没有在程序中体现出来啊

于是我把最后部分改成了

for(int i=0;i<=n;i++)
    {
        if(flag[MAX(1,i,flag)]+flag2[MAX(i,n,flag2)]-1>max)
            max=flag[MAX(1,i,flag)]+flag2[MAX(i,n,flag2)]-1;
    }

将最后部分替换，代码变成了这样（前面不变）

#include <stdio.h>
#include <stdlib.h>
int num[105],flag[105],flag2[105];
int MAX(int l,int r,int *num)
{
    int max=l;
    for(int i=l+1;i<=r;i++)
    {
        if(num[i]>num[max]) max=i;
    }
    return max;
}

int main()
{
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&num[i]);
        flag[i]=flag2[i]=1;
    }
    for(int i=2;i<=n;i++)  //dp1
    {
        for(int k=1;k<i;k++)
            if(num[i]>num[k] && flag[k]+1>flag[i])
                flag[i]=flag[k]+1;
    }
    for(int i=n-1;i>=1;i--)  //dp2
    {
        for(int k=n;k>i;k--)
            if(num[i]>num[k] && flag2[k]+1>flag2[i])
                flag2[i]=flag2[k]+1;
    }
    int max=0;
    for(int i=0;i<=n;i++)	//max
    {
        if(flag[MAX(1,i,flag)]+flag2[MAX(i,n,flag2)]-1>max)
            max=flag[MAX(1,i,flag)]+flag2[MAX(i,n,flag2)]-1;
    }
    printf("%d\n",n-max);
    return 0;
}

同样AC了

第二种我很好理解，但是第一种为什么会AC呢？

我觉得应该会存在i对应的dp1数组和dp2数组不是最大值的情况，那就不能简答地将flag[i]，flag2[i]相加了。

是数据弱的原因吗，还是这两种方法实际上是等效的