题解 | #拦截导弹#

最大递增子序列 坑点：注意状态转移方程 dp[i] = max{dp[j]+1,dp[i]} 0<=j<=i<=n (因为dp[i]会记录之前的暂定最长dp[i])

#include<iostream>
#include<string>
#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
int getNum(int t[],int n){
    
    int *dp = new int[n]();
    for(int i =0;i<n;i++){
        dp[i] = 1;
    }
    if(n==1)return 1;
    if(n==0)return 0;
    for(int i = 0;i<n;i++){
        //dp[i] = 1;
        for(int j =0;j<i;j++){
            if(t[j]>=t[i])
            dp[i] = max(dp[j]+1,dp[i]);
        }
    }
    int result = *max_element(dp,dp+n);
    delete []dp;
    return result;
    
}
int main(){
    int n;
    while(cin>>n){
        int t[n];
        for(int i =0;i<n;i++){
            cin>>t[i];
        }
        cout<<getNum(t,n)<<"\n";
    }
}