题目:

B3637 最长上升子序列 - 洛谷

输入样例:                             

6                                                
1 2 4 1 3 4

输出:

4

思路:

在脑中模拟挑选过程,我们会发现判断一个数能否加入已有的上升序列,我们关注的永远是它是否比序列最后一个数大,我们由此得到思路以每个数作为序列的最后一个数,得到以该数作为最后一个数的最长上升序列,最后从所有序列中得到最长上升子序列.

代码:

#include<bits/stdc++.h>
using namespace std;
int arr[5005];
int dp[5005];
int main(){
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>arr[i];
        dp[i]=1;//序列中只有arr[i]这个数的时候  例子:n个数全相同时,最长上升子序列的长度为1.
    }
    for(int i=1;i<=n;i++){
        for(int j=i-1;j>=1;j--){
            if(arr[j]<arr[i]){//判断arr[i]是否可以加在以arr[j]为最后一个数的最长序列中
                dp[i]=max(dp[i],dp[j]+1);
            }
        }
        //得到以arr[i]作为最后一个数的最长序列
    }
    int Max=0;
    for(int i=1;i<=n;i++){
        if(dp[i]>Max){
            Max=dp[i];
        }
    }
    cout<<Max;
    return 0;
}

结语:

感谢阅读