本文主要是介绍【晴问算法】提高篇—动态规划专题—最长上升子序列，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目描述
现有一个整数序列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;
}这篇关于【晴问算法】提高篇—动态规划专题—最长上升子序列的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
