关于动态规划合唱队问题的疑问！(语言-c语言)

Question

您的程序未能在规定时间内运行结束，请检查是否循环有错或算法复杂度过大。

通俗来说，能找到一个同学，他的两边的同学身高都依次严格降低的队形就是合唱队形。
例子：
123 124 125 123 121 是一个合唱队形
123 123 124 122不是合唱队形，因为前两名同学身高相等，不符合要求
123 122 121 122不是合唱队形，因为找不到一个同学，他的两侧同学身高递减。

你的任务是，已知所有N位同学的身高，计算最少需要几位同学出列，可以使得剩下的同学排成合唱队形。

注意：不允许改变队列元素的先后顺序 且 不要求最高同学左右人数必须相等

数据范围： 1 \le n \le 3000 \1≤n≤3000

未通过样例:
124
16 103 132 23 211 75 155 82 32 48 79 183 13 91 51 172 109 102 189 121 12 120 116 133 79 120 116 208 47 110 65 187 69 143 140 173 203 35 184 49 245 50 179 63 204 34 218 11 205 100 90 19 145 203 203 215 72 108 58 198 95 116 125 235 156 133 220 236 125 29 235 170 130 165 155 54 127 128 204 62 59 226 233 245 46 3 14 108 37 94 52 97 159 190 143 67 24 204 39 222 245 233 11 80 166 39 224 12 38 13 85 21 47 25 180 219 140 201 11 42 110 209 77 136

预期输出：95

#include <stdio.h>

int leftsing(int *height,int num,int i){//以第i个同学为基准左边最长上升子序列
//前面i-1组中满足：1.height[j]<height[i]2.leftsing[j]为最大值；
    if(i>0){
      int max1=0,max2=0;
      for(int j=0;j<i;j++){
         if(leftsing(height,num,j)>max1&&height[j]<height[i]){
           max1=leftsing(height,num,j);
         }
         if(leftsing(height,num,j)>max2){
            max2=leftsing(height,num,j);
         }
      }
      if(max1>=max2){
        return max1+1;
      }
      else
        return max2;
    }
    else
    return 1;
}//该函数输出正常

int main() {
    int num=0;
    scanf("%d",&num);
    int height[num];
    for(int i=0;i<num;i++){
        scanf("%d",&height[i]);
    }//以上输入正常，下面思考如何实现合唱队列
    int backheight[num];
    for(int i=0;i<num;i++){//对height进行倒序
       backheight[i]=height[num-1-i];
    }
    int best=0;
    for(int i=0;i<num;i++){//height的第i个数就是backheight的第num-1-i个数
       int temp=leftsing(height,num,i)+leftsing(backheight,num,num-i-1)-1;
       //temp越大越好
       if(temp>best)
          best=temp;
    }
    int min=num-best;
    printf("%d",min);
    return 0;
}

牛客刷题时遇到的问题，自测样例都能过，但是提交时就是0/20，而且报超时，用本地IDE输入错误的样例也是没有输出，很奇怪。

Answer 1

代码有一些问题。函数 leftsing 采用了递归的方式，这会导致程序在处理较大的输入时运行很慢，导致超时。此外程序没有处理可能出现的边界条件，例如 i 等于 0 时的情况。

提供一个思路：

首先，定义一个数组 dp，dp[i] 表示在前 i 个同学中出列最少的同学数，使得剩下的同学能排成合唱队形。

对于每个同学，有两种选择：

1、将其出列，这样的话，需要使得剩下的同学能排成合唱队形，就有 dp[i] = dp[i-1]。
2、将其保留，这样的话，需要使得它的左右两侧的同学身高都比它低，可以使用一个数组 left[i] 表示在第 i 个同学的左侧，最多能保留多少个比它高的同学，使得剩下的同学能排成合唱队形。同理，可以使用一个数组 right[i] 表示在第 i 个同学的右侧，最多能保留多少个比它低的同学，使得剩下的同学能排成合唱队形。就有 dp[i] =dp[i] = min(dp[i], dp[left[i]] + dp[right[i]] + 1)

于是，就可以得到状态转移方程：

dp[i] = min(dp[i-1], dp[left[i]] + dp[right[i]] + 1)

接下来，考虑如何求出 left[i] 和 right[i]。可以使用单调栈来维护一个递增的子序列。对于第 i 个同学，弹出栈中所有比它大的同学，并将它压入栈中。如果栈中有 k 个同学，就 left[i] = k，也就是在第 i 个同学的左侧最多能保留 k 个比它高的同学，使得剩下的同学能排成合唱队形。对于 right[i]，可以从后往前扫描数组，使用同样的方法求出。

程序输出 dp[n] 就可以了。

这是一种可行的做法，但是它的时间复杂度是 O(n^2)，可能还是不够优秀。如果想进一步优化，可以考虑使用更高效的算法，例如二分或者树状数组。
仅供参考，望采纳，谢谢。