溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
在C語言中，要找到一個字符串中的最長遞增子序列，可以使用動態規劃算法
#include<stdio.h>
#include<string.h>
int longestIncreasingSubsequence(const char *str) {
int n = strlen(str);
int dp[n];
for (int i = 0; i < n; i++) {
dp[i] = 1;
}
int maxLength = 1;
for (int i = 1; i < n; i++) {
for (int j = 0; j < i; j++) {
if (str[i] > str[j]) {
dp[i] = dp[i] > dp[j] + 1 ? dp[i] : dp[j] + 1;
}
}
maxLength = maxLength > dp[i] ? maxLength : dp[i];
}
return maxLength;
}
int main() {
const char *str = "ABCAGH";
printf("The length of the longest increasing subsequence in \"%s\" is: %d\n", str, longestIncreasingSubsequence(str));
return 0;
}
這個程序首先計算字符串的長度，然后創建一個動態規劃數組dp，用于存儲每個位置的最長遞增子序列長度。接下來，程序遍歷字符串中的每個字符，并更新dp數組。最后，程序返回dp數組中的最大值，即最長遞增子序列的長度。
在這個例子中，輸入字符串為"ABCAGH"，輸出結果為：The length of the longest increasing subsequence in “ABCAGH” is: 4。最長遞增子序列是"ABCG"。
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
