字符串最长升序子序列C语言代码

以下是字符串最长升序子序列的C语言代码：

#include <stdio.h>
#include <string.h>

int LIS(char s[])
{
    int len = strlen(s);
    int dp[len], max = 1;
    memset(dp, 1, sizeof(dp));

    for (int i = 1; i < len; i++)
    {
        for (int j = 0; j < i; j++)
        {
            if (s[j] < s[i] && dp[j] + 1 > dp[i])
            {
                dp[i] = dp[j] + 1;
                if (dp[i] > max)
                {
                    max = dp[i];
                }
            }
        }
    }
    return max;
}

int main()
{
    char s[100];
    scanf("%s", s);
    printf("%d", LIS(s));
    return 0;
}

该代码使用动态规划的思想，通过 dp 数组记录以当前字符结尾的最长升序子序列的长度。具体实现细节请看代码注释。

相关问题

Python字符串最长递增子序列代码

根据提供的引用内容，最长递增子序列的Python代码已经给出。但是，最长递增子序列是针对数字序列的，而不是字符串。如果要找到字符串的最长递增子序列，需要将字符串转换为数字序列，例如将字符串中的每个字符转换为其ASCII码值。下面是一个示例代码：

def lengthOfLIS(s: str) -> int:
    nums = [ord(c) for c in s] # 将字符串转换为数字序列
    n = len(nums)
    dp = [1] * n
    for i in range(1, n):
        for j in range(i):
            if nums[i] > nums[j]:
                dp[i] = max(dp[i], dp[j] + 1)
    return max(dp)

该代码使用动态规划算法，时间复杂度为$O(n^2)$。其中，dp[i]表示以第i个字符结尾的最长递增子序列的长度。在计算dp[i]时，需要遍历前面的所有字符j，如果nums[i] > nums[j]，则可以将第i个字符加入到以第j个字符结尾的最长递增子序列中，从而得到以第i个字符结尾的更长的递增子序列。

两个字符串的最长公共子序列长度_求2个字符串的最长公共子序列和最长公共子字符串的c语言代码

好的，下面是求解最长公共子序列和最长公共子字符串的C语言代码：

1. 求解最长公共子序列

int longest_common_subsequence(char* s1, char* s2) {
    int m = strlen(s1), n = strlen(s2);
    int dp[m+1][n+1];
    memset(dp, 0, sizeof(dp));
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (s1[i-1] == s2[j-1]) {
                dp[i][j] = dp[i-1][j-1] + 1;
            } else {
                dp[i][j] = fmax(dp[i-1][j], dp[i][j-1]);
            }
        }
    }
    return dp[m][n];
}

2. 求解最长公共子字符串

char* longest_common_substring(char* s1, char* s2) {
    int m = strlen(s1), n = strlen(s2);
    int dp[m+1][n+1];
    memset(dp, 0, sizeof(dp));
    int max_len = 0;
    int end_pos = 0;
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (s1[i-1] == s2[j-1]) {
                dp[i][j] = dp[i-1][j-1] + 1;
                if (dp[i][j] > max_len) {
                    max_len = dp[i][j];
                    end_pos = i;
                }
            } else {
                dp[i][j] = 0;
            }
        }
    }
    char* res = (char*)malloc(sizeof(char) * (max_len + 1));
    strncpy(res, s1 + end_pos - max_len, max_len);
    res[max_len] = '\0';
    return res;
}

这两段代码同样使用动态规划的思想来解决最长公共子序列和最长公共子字符串问题。其中，dp[i][j] 表示第一个字符串的前 i 个字符和第二个字符串的前 j 个字符之间的最长公共子序列（或子字符串）长度。最终的最长公共子序列（或子字符串）长度为 dp[m][n]，其中 m 和 n 分别为两个字符串的长度。通过倒推 dp 数组，我们可以得到最长公共子序列（或子字符串）具体是哪些字符。注意，在C语言中需要手动分配和释放内存。