基础算法题 —— 合唱队（最长递增子序列）

题解

①、枚举每个位置左右侧分别所能站的做多人
自左向右递增：求每个位置左边最多可站多少人（含自己）— dp1
自右向左递增：求每个位置右边最多可站多少人（含自己）— dp2
②、选择第 i 个位置不移动的情况下，合唱队所能站的人数：dp1[i]+dp2[i]-1
合唱队最多人：Max_ = dp1[i]+dp2[i]-1
③、组成合唱队移除最少人：n - Max_

代码

#include<bits/stdc++.h>
using namespace std;

int main() {
    int n, arr[3000], dp1[3000], dp2[3000];
    cin>>n;
    for(int i=0; i<n; i++) {
        cin>>arr[i];
        dp1[i] = 1;
        for(int j=0; j<i; j++) {
            if(arr[i]>arr[j])
            dp1[i] = max(dp1[i], dp1[j]+1);
        }
    }
    for(int i=n-1; i>=0; i--) {
        dp2[i] = 1;
        for(int j=n-1; j>=i; j--) {
            if(arr[i]>arr[j])
            dp2[i] = max(dp2[i], dp2[j]+1);
        }
    }
    
    int Max_ = 0;
    for(int i=0; i<n; i++) {
        Max_ = max(dp1[i]+dp2[i]-1, Max_);
    }
    cout<<n-Max_;
    
    return 0;
}