✏️ 纠错
第 164 题 / 共 201 题
第13题 下面 LIS函数试图求出最长上升子序列的长度,横线处应该填入的是( )。
int max(int a, int b) {
return (a > b) ? a : b;
}
int LIS(vector<int> &nums) {
int n = nums.size();
if (n == 0)
return 0;
vector<int> dp(n, 1);
int maxLen = 1;
for (int i = 1; i < n; i++) {
for (int j = 0; j < i; j++)
if (nums[j] < nums[i])
______; // 在此处填入选项
maxLen = max(maxLen, dp[i]);
}
return maxLen;
}你真棒!
📝 题目解析
答案:D
考纲知识点:线性DP
解析:本题考察LIS的状态转移方程,DP[i]为以nums[i]为结尾的LIS的长度,对nums[i],考虑前方的j,衔接某个nums[j],满足nums[j]<nums[i],则i可以衔接到j结尾,组成长度+1的LIS;