单调递增最大子序列C++代码
时间: 2023-11-14 22:31:20 浏览: 35
#include <iostream>
#include <vector>
using namespace std;
int main()
{
int n;
cin >> n;
vector<int> nums(n);
for (int i = 0; i < n; i++) {
cin >> nums[i];
}
vector<int> dp(n, 1);
int max_len = 1;
for (int i = 1; i < n; i++) {
for (int j = 0; j < i; j++) {
if (nums[j] < nums[i]) {
dp[i] = max(dp[i], dp[j] + 1);
}
}
max_len = max(max_len, dp[i]);
}
cout << max_len << endl;
return 0;
}
相关问题
找一个序列的最长单调递增子序列的c++代码
以下是使用动态规划算法求解最长单调递增子序列的C++代码:
```c++
#include <iostream>
#include <vector>
using namespace std;
int main() {
vector<int> nums = {10, 9, 2, 5, 3, 7, 101, 18}; // 待求解的序列
int n = nums.size(); // 序列长度
vector<int> dp(n, 1); // dp数组,存储以每个元素为结尾的最长递增子序列长度
int res = 1; // 最长递增子序列长度
for (int i = 1; i < n; i++) {
for (int j = 0; j < i; j++) {
if (nums[i] > nums[j]) {
dp[i] = max(dp[i], dp[j] + 1); // 状态转移方程
}
}
res = max(res, dp[i]); // 更新最长递增子序列长度
}
cout << res << endl; // 输出结果
return 0;
}
```
在上述代码中,我们使用了一个长度为n的dp数组,其中dp[i]表示以第i个元素为结尾的最长递增子序列的长度。然后我们遍历整个序列,对于每一个元素,我们再遍历它之前的所有元素,如果发现当前元素比之前的某个元素大,那么就可以将当前元素加入到该元素所在的最长递增子序列中,从而得到以当前元素为结尾的最长递增子序列。最后,我们取所有的以每个元素为结尾的最长递增子序列长度中的最大值,即可得到整个序列的最长递增子序列长度。
P1309 最长单调递增子序列
这是一道经典的动态规划问题,可以使用 O(n^2) 的时间复杂度解决。具体的解题思路如下:
1. 定义一个数组 dp,其中 dp[i] 表示以第 i 个数为结尾的最长单调递增子序列的长度。
2. 初始时,所有的 dp[i] 都为 1,因为每个数本身就是一个长度为 1 的单调递增子序列。
3. 对于第 i 个数,遍历它之前的所有数 j,如果当前数 nums[i] 大于 nums[j],则可以将第 j 个数加入到以第 i 个数为结尾的子序列中,此时 dp[i] 的值就可以更新为 dp[j]+1。
4. 最终的答案就是 dp 数组中的最大值。
代码实现如下:
```c++
int n;
int nums[MAXN], dp[MAXN];
int main() {
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> nums[i];
dp[i] = 1;
}
int ans = 1;
for (int i = 2; i <= n; i++) {
for (int j = 1; j < i; j++) {
if (nums[i] > nums[j]) {
dp[i] = max(dp[i], dp[j] + 1);
}
}
ans = max(ans, dp[i]);
}
cout << ans << endl;
return 0;
}
```