CSDN竞赛63期题解

**CSDN竞赛63期题解**

本期题目为：

**[63期] 最长上升子序列 II**

给定一个长度为 n 的整数数组 arr，要求找到最长上升子序列（LIS）的长度。

注意：这个问题的难度比之前的版本高，因为我们需要考虑到子序列中可以出现重复元素的情况。

**题解**

###1. 动态规划我们首先尝试使用动态规划来解决这个问题。我们定义一个一维数组 dp，长度为 n+1，dp[i] 表示 arr 中前 i 个数字的最长上升子序列的长度。

cppint findLIS(int* arr, int n) {
 int dp[n +1];
 for (int i =0; i <= n; i++) {
 dp[i] =1;
 }
 for (int i =1; i <= n; i++) {
 for (int j =0; j < i; j++) {
 if (arr[i -1] > arr[j -1]) {
 dp[i] = max(dp[i], dp[j] +1);
 }
 }
 }
 int maxLIS =0;
 for (int i =0; i <= n; i++) {
 maxLIS = max(maxLIS, dp[i]);
 }
 return maxLIS;
}

###2. 二分查找我们可以使用二分查找来找到 arr 中第一个大于等于给定值的元素。

cppint findFirstGreater(int* arr, int n, int target) {
 int left =0;
 int right = n -1;
 while (left <= right) {
 int mid = left + (right - left) /2;
 if (arr[mid] >= target) {
 right = mid -1;
 } else {
 left = mid +1;
 }
 }
 return left == n ? -1 : arr[left];
}

###3. 最长上升子序列 II我们可以使用二分查找来找到 arr 中第一个大于等于给定值的元素，然后将该元素添加到最长上升子序列中。

cppint findLISII(int* arr, int n) {
 int dp[n +1];
 for (int i =0; i <= n; i++) {
 dp[i] =1;
 }
 for (int i =1; i <= n; i++) {
 int target = arr[i -1];
 int index = findFirstGreater(arr, n, target);
 if (index == -1) {
 dp[i] =1;
 } else {
 dp[i] = dp[index] +1;
 }
 }
 int maxLIS =0;
 for (int i =0; i <= n; i++) {
 maxLIS = max(maxLIS, dp[i]);
 }
 return maxLIS;
}

###4. 测试我们可以使用以下测试用例来测试我们的函数。

cppint main() {
 int arr[] = {10,22,9,33,21,50,41,60};
 int n = sizeof(arr) / sizeof(arr[0]);
 printf("最长上升子序列的长度：%d
", findLISII(arr, n));
 return0;
}

###5. 结论我们可以使用动态规划和二分查找来解决这个问题。我们的函数 `findLISII` 可以找到最长上升子序列的长度。

**注释**

* 我们定义了一个一维数组 dp，长度为 n+1，dp[i] 表示 arr 中前 i 个数字的最长上升子序列的长度。
* 我们使用二分查找来找到 arr 中第一个大于等于给定值的元素。
* 我们将该元素添加到最长上升子序列中。
* 我们可以使用以下测试用例来测试我们的函数。

**参考**

* [63期] 最长上升子序列 II* 动态规划* 二分查找