K12教育赛事综合服务平台
聚乐之家官方网站
下载聚乐之家官方App
专注青少年竞赛题库网站
已知数组下标从0开始计数,子序列要求元素严格递增。
dp数组的初始值全部为1,因为每个元素本身就是长度为1的子序列
状态转移方程为dp[i] = max(dp[j] + 1) ,其中j的范围是0 ≤ j < i 且 nums[j] < nums[i],若无满足条件的j则dp[i]保持初始值
该DP解法的时间复杂度为O(n),空间复杂度为O(n)
整个数组的最长递增子序列的长度为dp数组中的最大值