C语言求最大长度子串 - 动态规划实现

以下是一个求最大长度子串的 C 语言代码，采用动态规划的思想：

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

int max(int a, int b) {
    return a > b ? a : b;
}

int maxSubStr(char* str) {
    int len = strlen(str);
    int dp[len];
    int maxLen = 0;
    dp[0] = 1;
    for (int i = 1; i < len; i++) {
        dp[i] = 1;
        for (int j = 0; j < i; j++) {
            if (str[i] > str[j]) {
                dp[i] = max(dp[i], dp[j] + 1);
            }
        }
        maxLen = max(maxLen, dp[i]);
    }
    return maxLen;
}

int main() {
    char str[] = 'abcdeafg';
    int maxLen = maxSubStr(str);
    printf('The maximum length of substring is %d\n', maxLen);
    return 0;
}

运行结果：

The maximum length of substring is 7

解释：

该程序采用动态规划的思想，定义一个一维数组 dp，其中 dp[i] 表示以第 i 个字符结尾的最长子串的长度。初始化 dp[0] 为 1，表示第一个字符的最长子串长度为 1。然后从第二个字符开始遍历整个字符串，对于每个字符 i，遍历前面的所有字符 j，如果 str[i] > str[j]，则 dp[i] 可以更新为 dp[j] + 1，表示以第 j 个字符结尾的最长子串再加上当前字符 i 可以构成一个更长的子串。最后遍历完整个字符串后，dp 数组中的最大值即为最长子串的长度。