一开始想到的方法非常低效，但好理解。
思路分析：
使用二维数组dp来记录递增子序列的长度信息，其中dp[i][0]表示以nums[i]结尾的最长递增子序列的长度，dp[i][1]表示包含nums[i]的最长递增子序列的长度。 初始化dp数组，将以第一个元素结尾的递增子序列长度置为0。 使用两层循环遍历数组，比较当前元素与前面元素的大小关系，更新dp数组的值。 最终返回最后一个元素的两种状态中的最大值，即为整个数组的最长递增子序列的长度。
这种动态规划算法的时间复杂度为O(n^2)，其中n为数组的长度。
class Solution {
public:
// 函数用于计算最长递增子序列的长度
int lengthOfLIS(vector
// dp[i][0]表示以nums[i]结尾的最长递增子序列的长度
// dp[i][1]表示包含nums[i]的最长递增子序列的长度
vector
// 初始化dp数组，将以第一个元素结尾的递增子序列长度置为0
dp[0][0] = 0;
// 遍历数组，计算dp数组的值
for (int i = 1; i < nums.size(); i++) {
for (int j = i - 1; j >= 0; j--) {
// 如果当前元素大于前面的某个元素，更新包含当前元素的递增子序列的长度
if (nums[i] > nums[j]) {
dp[i][1] = max(dp[i][1], dp[j][1] + 1);
}
// 更新以当前元素结尾的递增子序列的长度
dp[i][0] = max(dp[i][0], max(dp[j][1], dp[j][0]));
}
}
// 返回最终结果，取最后一个元素的两种状态中的最大值
return max(dp[nums.size() - 1][0], dp[nums.size() - 1][1]);
}
};
但还有种节省空间的方法。
思路分析：
初始化dp数组，其中dp[i]表示以第i个元素结尾的最长递增子序列的长度，初始值为1。 使用两层循环遍历数组，对于每个元素，查找在其之前的元素中比它小的元素，更新以当前元素结尾的最长递增子序列的长度。 在内循环中，通过比较当前元素与之前元素的大小关系，更新dp数组的值。 同时，记录整个数组的最长递增子序列的长度，即取dp数组中的最大值。 最终返回整个数组的最长递增子序列的长度。
这种算法的时间复杂度为O(n^2)，其中n为数组的长度。
class Solution {
public:
// 函数用于计算最长递增子序列的长度
int lengthOfLIS(vector
// 如果数组长度小于等于1，直接返回数组长度
if (nums.size() <= 1) return nums.size();
// dp数组用于记录以每个元素结尾的最长递增子序列的长度
vector
// result用于记录整个数组的最长递增子序列的长度
int result = 0;
// 遍历数组
for (int i = 1; i < nums.size(); i++) {
// 在当前元素之前的元素中查找比当前元素小的元素
for (int j = 0; j < i; j++) {
// 如果找到比当前元素小的元素，更新以当前元素结尾的最长递增子序列的长度
if (nums[i] > nums[j]) {
dp[i] = max(dp[i], dp[j] + 1);
}
}
// 更新整个数组的最长递增子序列的长度
if (dp[i] > result) {
result = dp[i];
}
}
// 返回最终结果，即整个数组的最长递增子序列的长度
return result;
}
};
但是这两种方法都是时间复杂度为O（n²）的方法，在有些情况下无法通过。 那么还能不能更新优化，使得时间复杂度更低呢？
思路分析：
首先定义了一个辅助函数 check，用于在有序数组中查找第一个大于等于给定值的元素的索引。主函数 lengthOfLIS 开始时初始化了一个长度为 n+1 的数组 dp1，用于保存不同长度的递增子序列的末尾元素的最小值。然后遍历给定的数组 nums，对于每一个元素，判断其与当前保存的递增子序列的末尾元素的大小关系。如果当前元素大于当前递增子序列的末尾元素，则将其直接加入当前递增子序列，更新长度和末尾元素。如果当前元素小于等于当前递增子序列的末尾元素，则在 dp1 数组中使用 check 函数找到一个位置，将当前元素替换进去。这个位置就是当前元素要插入的位置。最终返回 len，即最长递增子序列的长度。
该算法的时间复杂度为 O(nlogn)，其中 n 为给定数组 nums 的长度。
class Solution {
// 辅助函数：在有序数组dp中查找第一个大于等于x的元素的索引
int check(int x, vector
int mid;
while (left <= right) {
mid = (left + right) / 2;
if (dp[mid] < x) {
if (dp[mid + 1] >= x)
return mid + 1; // 返回第一个大于等于x的位置
else
left = mid + 1; // 在右半部分继续查找
} else
right = mid - 1; // 在左半部分查找
}
return 1; // 如果未找到大于等于x的元素，则返回1
}
public:
// 主函数：求解最长递增子序列的长度
int lengthOfLIS(vector
int n = nums.size();
vector
dp1[1] = nums[0]; // 初始化，长度为1的递增子序列的末尾元素为nums[0]
int len = 1; // 初始递增子序列的长度为1
for (int i = 1; i < n; i++) {
if (nums[i] > dp1[len]) {
len++; // 如果当前元素大于当前递增子序列的末尾元素，则将其加入到当前递增子序列中
dp1[len] = nums[i];
} else
dp1[check(nums[i], dp1, 1, len)] = nums[i]; // 否则，在dp1中寻找适合的位置替换
}
return len; // 返回最长递增子序列的长度
}
};
精彩链接
您阅读本篇文章共花了：
发表评论