---

dp专题18 最长上升子序列

原创 于 2024-01-27 13:41:27 发布 · 粉丝可见 · 398 阅读 · 4 · 4 · 本内容遵循CC 4.0 BY-SA版权协议 版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。 GEO检测 · 编辑
文章链接：https://blog.csdn.net/hacker_51/article/details/135867431

本题链接： 晴问算法

题目：

样例：

cobol<br/>7<br/>1 2 3 -1 -2 7 9<br/>

5

思路：

根据题目意思,求出最长上升子序列，不是递减的序列。

子序列的含义是：      在原数组中选取元素，选取的元素顺序和在原数组中的顺序是一致的

从中，由于是上升的子序列，所以我们只能从头到尾的选取。

这里我们明确一下dp[ i ] 的含义，由于我们是从头到尾的选取，寻找最长的上升子序列，

所以我们确定   dp[ i ] 含义就是当前下标  i  的最长上升子序列长度是多少。其中 i 就是原数组的下标位置。

所以得出一个 for  循环

for(int i = 1;i < nums.size();++i)

又因为我们是从头到尾的一个一个进行查看当前下标 i 的选取，所以又得到一个 for 循环作为选取元素作用

for(int j = 0;j < i;++j)

确定好遍历顺序后，明确 dp初始化，  由于我们最长上升子序列，所以，我们最少都有一个长度 1 作为上升子序列，所以 dp 初始化可以 是 都为 1.

确定 dp 公式，我们是  最长上升子序列，所以我们选取的过程中，判断一下，当前的 i 的元素是否大于或者等于 我们选取的之前的元素的最大，然后取 max 即可。

if(nums[i] >= nums[j]) dp[i] = max(dp[i],dp[j] + 1);

代码详解如下：

#include <iostream>
#include <vector>
#include <algorithm>
#define endl '\n'
#define IOS ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
using namespace std;
 
inline int lengthOfLIS(vector<int>& nums) 
{
	int sz = nums.size();
	vector<int>dp(sz + 1,1);	// dp 初始化 1	
	int ans = 1;
	for(int i = 1;i < sz;++i)
	{
		for(int j = 0;j < i;++j)
		{
			if(nums[i] >= nums[j]) dp[i] = max(dp[i],dp[j] + 1);
		}
		ans = max(ans,dp[i]);	// 寻找最长上升子序列长度的 记录
	}
	return ans;
}
 
int main()
{
	IOS;
	int n;
	vector<int>v;
	cin >> n;
	while(n--)
	{
		int x;
		cin >> x;
		v.emplace_back(x);
	}
	
	int ans = lengthOfLIS(v);
	
	cout << ans << endl;
	
	return 0;
}

最后提交：