关于C++实现线性动态规划求解最长递增子序列（LIS）问题，下列说法错误的是？

rg929809 单选题共个子题

已知给定长度为n的整数数组arr，需要求解其中严格最长递增子序列的长度，子序列指序列中删除部分或不删除元素得到的、不改变剩余元素顺序的序列。

定义dp[i]表示以第i个元素结尾的最长递增子序列长度，初始值dp[i] = 1，状态转移方程为dp[i] = max(dp[i], dp[j] + 1)，其中0 ≤ j < i 且 arr[j] < arr[i]，该解法时间复杂度为O(n²)

可以通过贪心+二分查找的方法将LIS问题的时间复杂度优化到O(nlogn)，该优化方法属于线性动态规划的优化实现范畴

线性动态规划的核心特点是状态转移仅依赖于前面已经计算完成的前置状态，求解顺序按照序列的线性顺序从前到后递推

如果将问题改为求最长非递减子序列，只需要将O(n²)解法中状态转移的判断条件arr[j] < arr[i]修改为arr[j] <= arr[i]，同时dp数组的初始值需要修改为0

正在加载题目数据…

第空

已答 /

子题

第空

提示

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

答案解析