以下关于最长上升子序列（LIS）问题的C++线性动态规划解法，描述正确的是？

qi118012 单选题共个子题

已知长度为n的整数数组nums，要求计算其最长严格上升子序列的长度，子序列不要求连续。

定义dp[i]表示前i个元素组成的数组的最长上升子序列长度，转移方程为dp[i] = max(dp[i-1], dp[j]+1) 其中j<i且nums[j]<nums[i]

定义dp[i]表示以第i个元素结尾的最长上升子序列长度，转移方程为dp[i] = 1 + max{ dp[j] | j < i 且 nums[j] < nums[i] }，无满足条件的j时dp[i]=1

定义dp[i]表示以第i个元素结尾的最长上升子序列长度，转移方程为dp[i] = nums[i] > nums[i-1] ? dp[i-1]+1 : 1

该线性动态规划解法的时间复杂度为O(n)，空间复杂度为O(n)

正在加载题目数据…

第空

已答 /

子题

第空

提示

该题型需在试卷/作业中作答，单题练习暂不支持

答案解析