最长下降子序列c++实现代码
时间: 2023-11-12 21:05:35 浏览: 41
以下是最长下降子序列的 C 语言实现代码:
```
#include <stdio.h>
int LDS(int arr[], int n) {
int lds[n];
lds[0] = 1;
for (int i = 1; i < n; ++i) {
lds[i] = 1;
for (int j = 0; j < i; ++j) {
if (arr[i] < arr[j] && lds[i] < lds[j] + 1) {
lds[i] = lds[j] + 1;
}
}
}
int max = 0;
for (int i = 0; i < n; ++i) {
if (lds[i] > max) {
max = lds[i];
}
}
return max;
}
int main() {
int arr[] = {15, 27, 14, 38, 63, 55, 46, 65, 85, 27};
int n = sizeof(arr) / sizeof(arr[0]);
printf("最长下降子序列的长度为:%d", LDS(arr, n));
return 0;
}
```
该程序的输出为:最长下降子序列的长度为:4
相关问题
最长公共子序列C++代码实现
以下是最长公共子序列的 C++ 代码实现:
```cpp
#include <iostream>
#include <cstring>
using namespace std;
int lcs(string X, string Y, int m, int n)
{
int L[m+1][n+1];
for (int i=0; i<=m; i++)
{
for (int j=0; j<=n; j++)
{
if (i == 0 || j == 0)
L[i][j] = 0;
else if (X[i-1] == Y[j-1])
L[i][j] = L[i-1][j-1] + 1;
else
L[i][j] = max(L[i-1][j], L[i][j-1]);
}
}
return L[m][n];
}
int main()
{
string X = "AGGTAB";
string Y = "GXTXAYB";
int m = X.length();
int n = Y.length();
cout << "Length of LCS is: " << lcs(X, Y, m, n) << endl;
return 0;
}
```
输出结果为:
```
Length of LCS is: 4
```
其中,L[m+1][n+1]表示长度为 m 和 n 的两个字符串的最长公共子序列的长度,X[i-1]表示第一个字符串 X 的第 i 个字符,Y[j-1]表示第二个字符串 Y 的第 j 个字符。
最长公共子序列问题C++代码实现
以下是最长公共子序列问题的 C++ 代码实现:
```cpp
#include <iostream>
#include <cstring>
using namespace std;
int LCS(string str1, string str2, int m, int n) {
int dp[m + 1][n + 1];
for (int i = 0; i <= m; i++) {
for (int j = 0; j <= n; j++) {
if (i == 0 || j == 0) {
dp[i][j] = 0;
}
else if (str1[i - 1] == str2[j - 1]) {
dp[i][j] = dp[i - 1][j - 1] + 1;
}
else {
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
}
}
}
return dp[m][n];
}
int main() {
string str1 = "AGGTAB";
string str2 = "GXTXAYB";
int m = str1.size();
int n = str2.size();
cout << "Length of LCS: " << LCS(str1, str2, m, n) << endl;
return 0;
}
```
在这个实现中,我们定义一个二维数组 `dp` 来存储最长公共子序列的长度。我们使用动态规划来解决问题。对于每个字符 `str1[i-1]` 和 `str2[j-1]`,我们可以有两种选择:
1. 如果它们相等,则它们一定属于最长公共子序列,因此我们将它们添加到最长公共子序列中,并将长度加一。此时,我们需要在 `str1[0:i-2]` 和 `str2[0:j-2]` 中找到最长公共子序列。
2. 如果它们不相等,则它们不能同时出现在最长公共子序列中。这意味着我们需要找到 `str1[0:i-2]` 和 `str2[0:j-1]` 或 `str1[0:i-1]` 和 `str2[0:j-2]` 中的最长公共子序列。
我们使用 `dp[i][j]` 存储 `str1[0:i-1]` 和 `str2[0:j-1]` 的最长公共子序列的长度。我们可以通过填充 `dp` 数组来计算最长公共子序列的长度。具体来说,对于任意 `i` 和 `j`,如果 `str1[i-1]` 和 `str2[j-1]` 相等,则 `dp[i][j]` 等于 `dp[i-1][j-1] + 1`,否则 `dp[i][j]` 等于 `max(dp[i-1][j], dp[i][j-1])`。最终,我们将返回 `dp[m][n]`,其中 `m` 和 `n` 是 `str1` 和 `str2` 的长度。