CSDN 周赛 62 期

**CSDN 周赛62 期**

### 题目描述本周赛的题目是 "最长上升子序列"，要求我们找出一个给定整数数组中，最长的连续上升子序列。

### 题目分析这个问题可以用动态规划来解决。我们需要维护一个长度为 n 的数组 dp，其中 dp[i] 表示以 i 为结尾的最长上升子序列的长度。

###代码实现

cpp#include <iostream>
using namespace std;

int longestIncreasingSubsequence(int arr[], int n) {
 // 初始化动态规划数组 int dp[n];
 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] > arr[j]) {
 dp[i] = max(dp[i], dp[j] +1);
 }
 }
 }

 // 找到最长上升子序列的长度 int maxLength =1;
 for (int i =0; i < n; i++) {
 if (dp[i] > maxLength) {
 maxLength = dp[i];
 }
 }

 return maxLength;
}

// 测试函数void test() {
 int arr[] = {10,22,9,33,21,50,41,60};
 int n = sizeof(arr) / sizeof(arr[0]);
 cout << "最长上升子序列的长度是：" << longestIncreasingSubsequence(arr, n);
}

int main() {
 test();
 return0;
}