牛客热题：最长上升子序列(一)

本文主要是介绍牛客热题：最长上升子序列(一)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

📟作者主页：慢热的陕西人

🌴专栏链接：力扣刷题日记

📣欢迎各位大佬👍点赞🔥关注🚓收藏，🍉留言

牛客热题：最长上升子序列(一)

题目链接

最长上升子序列(一)_牛客题霸_牛客网 (nowcoder.com)

方法一：简单dp

思路

①状态表示

$dp[i]$表示以$arr[i]$为结尾的最长上升子序列的长度

②状态转移

$dp[i]=max(dp[i],d[j]+1)$

③初始化

对于所有的初始状态，都应该设置为1，因为对于以每一个位置结尾的最长上升子序列的长度最小为1

④填表顺序

外层循环，从左到右，内部循环，均可

⑤返回值

$dp[i]$中的最大值

代码

int LIS(vector<int>& arr) {int n = arr.size();if(n == 1) return 1;int res = 0;//dp[i]表示以arr[i]为结尾的最长的子序列的长度vector<int> dp(n, 1);for(int i = 1; i < n; ++i){for(int j = i - 1; j >= 0; --j){if(arr[i] > arr[j])dp[i] = max(dp[i], dp[j] + 1);}res = max(res, dp[i]);}return res;}

复杂度

时间复杂度：$O(N^2)$, 双层循遍历数组的同时，遍历当前节点之前的所有节点

空间复杂度：O(N), 额外使用了一个和原数组长度相同的dp数组

这篇关于牛客热题：最长上升子序列(一)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---