Niuke: intercepting missiles

  This problem is transformed into the problem of finding the longest increasing subsequence through a mathematical theorem .

First , The first question is obviously to find the longest non decreasing subsequence , The second question is to use a theorem , You can refer to ：

Dilworth What is the theorem _litble The blog of -CSDN Blog _dilworth Theorem

Finally, after transforming the problem , The solution is very simple , mathematics yyds, The code is as follows ：

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

//  Find the length of the longest non decreasing subsequence 
int solve1(vector<int> &height){
    int len=height.size();
    int res=INT_MIN;
    vector<int> dp(len, 1);
    for(int i=0;i<len;++i){
        for(int j=0;j<i;++j){
            if(height[i] <= height[j]){
                dp[i]=max(dp[i], dp[j]+1);
            }
        }
        res=max(res, dp[i]);
    }
    return res;
}

//  Find the length of the longest increasing subsequence 
int solve2(vector<int> &height){
    int len=height.size();
    int res=INT_MIN;
    vector<int> dp(len, 1);
    for(int i=0;i<len;++i){
        for(int j=0;j<i;++j){
            if(height[i] > height[j]){
                dp[i]=max(dp[i], dp[j]+1);
            }
        }
        res=max(res, dp[i]);
    }
    return res;
}

int main(){
    int n;
    cin>>n;
    vector<int> height(n);
    for(int i=0;i<n;++i){
        cin>>height[i];
    }
    int res1=solve1(height);
    int res2=solve2(height);
    cout<<res1<<endl<<res2<<endl;
    return 0;
}