K12教育赛事综合服务平台
聚乐之家官方网站
下载聚乐之家官方App
专注青少年竞赛题库网站
最长上升子序列指的是在一个给定的数值序列中，找到一个子序列，使得这个子序列元素的数值依次递增，并且这个子序列的长度尽可能大，子序列不要求元素在原序列中连续。
定义dp[i]表示以原数组第i个元素结尾的最长上升子序列长度，初始化时所有dp[i]的默认值为1
状态转移方程可以写为：对所有满足j < i的下标j，如果nums[i] > nums[j]，则dp[i] = max(dp[i], dp[j] + 1)
该线性DP解法的时间复杂度为O(n)，空间复杂度为O(n)（n为原数组长度）
最终求解得到的最长上升子序列长度是整个dp数组中的最大值