【晴问算法】提高篇—动态规划专题—最长上升子序列

题目描述

现有一个整数序列a1,a2,...,an​​​​​​，求最长的子序列（可以不连续），使得这个子序列中的元素是非递减的。输出该最大长度。

输入描述

第一行一个正整数n（1≤n≤100​​​​），表示序列长度；

第二行为用空格隔开的n​个整数ai​（−10^5≤ai≤10^5​​），表示序列元素。

输出描述

输出一个整数，表示最大长度。

样例1

输入

7

1 2 3 -1 -2 7 9

输出

5

解释

最长上升子序列为1 2 3 7 9，长度为5。

#include<bits/stdc++.h>
using namespace std;
const int MAXN = 100;
int dp[MAXN];//dp[i]表示以a[i]元素为结尾的最大连续子序列和
int a[MAXN];//存放序列元素int main(){int n;//序列长度cin >> n;for(int i=0;i<n;i++){cin >> a[i];}dp[0] = 1;for(int i=1;i<n;i++){//对于每个位置i，要找到以a[i]结尾的最长递增子序列长度dp[i]dp[i] = 1;//初始化为1，因为至少可以构成一个长度为1的子序列for(int j=0;j<i;j++){//检查是否可以将a[i]加入到以a[j]结尾的递增子序列中if(a[i] > a[j]){//说明a[i]可以接在以a[j]结尾后dp[i] = max(dp[j] + 1,dp[i]);//dp[j]+1表示接在了以a[j]结尾的子序列长度，更新以a[i]结尾的子序列长度}}}int ans = 1;for(int i=1;i<n;i++){//不是输出最后一个dp元素，因为最后一个元素不一定在递增子序列中if(ans < dp[i]){//遍历寻找以a[i]结尾最大的子序列ans = dp[i];}}printf("%d",ans);return 0;
}