动态规划求一串字符串最长单调子序列(c语言)

动态规划可以有效地解决寻找字符串中最长单调子序列的问题。这个经典的算法通常用于查找一个序列是否为单调递增或单调递减，或者找到其中最长的这样的子序列。下面是一个简单的C语言实现，以找出给定字符串的最长递增子序列：

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

int lengthOfLIS(char* str) {
    int n = strlen(str);
    int dp[n];
    dp[0] = 1; // 初始化空字符串的长度为1

    for (int i = 1; i < n; ++i) {
        dp[i] = 1;
        for (int j = 0; j < i; ++j) {
            if (str[i] > str[j]) { // 如果当前字符大于之前的某个字符
                dp[i] = max(dp[i], dp[j] + 1); // 更新最大长度
            }
        }
    }

    return *max_element(dp, dp + n); // 返回最长递增子序列的长度
}

// 定义一个辅助函数，返回两个整数的最大值
int max(int a, int b) {
    return a > b ? a : b;
}

int main() {
    char str[] = "10098765";
    printf("The longest increasing subsequence of the given string is: %d\n", lengthOfLIS(str));
    return 0;
}

在这个例子中，`lengthOfLIS` 函数使用了二维数组 `dp` 来存储每个位置到结束的最长递增子序列的长度。外部循环遍历字符串中的每个字符，内部循环则检查前面的字符以更新当前子序列的可能长度。