猿创征文 |【算法面试入门必刷】动态规划-线性dp（四）

【算法面试入门必刷】动态规划-线性dp（四）

• 前言
• 算法入门刷题训练
• • 题目AB37：最长上升子序列(一)
  • • 题目分析
    • 理论准备
    • 题解
    • 小结

      📦个人主页：一二三o-0-O的博客

      🏆技术方向：C/C++客户端资深工程师（直播+音视频剪辑）

      👨‍💻作者简介：数据结构算法与音视频领域创作者

      📒 系列专栏：牛客网面试必刷

      📣专栏目标：帮助伙伴们通过系统训练，掌握数据结构与算法，收获心仪Offer

      📝推荐一个找工作神器：牛客刷题网 【面试经验|实习招聘内推，求职就业一战解决】

      🧡如果对您有帮助的话，欢迎点赞👍收藏📂，关注不迷路

      【算法入门必刷】数据结构-栈篇系列文章：

      【算法入门必刷】数据结构-栈（一）

      【算法入门必刷】数据结构-栈（二）

      【算法入门必刷】数据结构-栈（三）

      【算法入门必刷】数据结构-栈（四）

      【算法入门必刷】数据结构-栈（五）

      【算法入门必刷】动态规划-线性dp篇系列文章：

      【算法面试入门必刷】动态规划-线性dp（一）

      【算法面试入门必刷】动态规划-线性dp（二）

      【算法面试入门必刷】动态规划-线性dp（三）

      前言

      开启刷题，请点击右边链接进行跳转点击这里

      

      算法入门刷题训练

      题目AB37：最长上升子序列(一)

      题目分析

      描述

      给定一个长度为 n 的数组 arr，求它的最长严格上升子序列的长度。

      所谓子序列，指一个数组删掉一些数（也可以不删）之后，形成的新数组。例如 [1,5,3,7,3] 数组，其子序列有：[1,3,3]、[7] 等。但 [1,6]、[1,3,5] 则不是它的子序列。

      我们定义一个序列是 严格上升 的，当且仅当该序列不存在两个下标 i 和 j 满足 i}; // 求得从下标0到下标i-1中dp值的最大值 for(int j{};j // 当当前值大于v[j]，才进行dp[j]的判断 if(v[i] v[j]){ maxValue = max(maxValue,dp[j]); } } // 然后dp[i]就等于之前的最大的连续子序列的长度加上当前数值 dp[i] = maxValue + 1; 1};i int maxValue{}; // 内部从小到大，从大到小都可以 for(int j{};j if(v[i] v[j]){ maxValue = max(maxValue,dp[j]); } } } int n; cin n; vector v(n); for(int i{};i> v[i]; // dp[i] 表示以第i个数字为结尾的最长连续子序列的长度 vector dp(n,1); int result{}; for(int i{1};i int maxValue{}; for(int j{};j if(v[i] v[j]){ maxValue = max(maxValue,dp[j]); } } dp[i] = maxValue + 1; if(dp[i] result) result = dp[i]; } cout