最长不下降+最长不上升子序列

这是一道动态规划的题。序列中最少需要的拦截系统的数量等于最长不下降子序列的长度。

#include<bits/stdc++.h>
using namespace std;
int main(){
    int c, n=1;
    int a[1000005];
    while(cin >> c){
        a[n++] = c;
    }
    n--;
    vector<int> dp(n+2, 1);
    vector<int> dp2(n+2, 1);
    int mx = 1;
    int mn = 1;
    for(int i=2; i<=n; i++){
        for(int j=1; j<i; j++){
            if(a[j]>=a[i]){
                dp[i]=max(dp[i], dp[j]+1);
            }
            if(a[j]<=a[i]){
                dp2[i] = max(dp2[i], dp2[j]+1);
            }
        }
        mx = max(mx, dp[i]);
        mn = max(mn, dp2[i]);
        
    }
    cout << mx << endl << mn;
}