c语言最长递增子序列

求解最长递增子序列有多种算法，以下是一种基于动态规划的解法，使用C语言实现：

#include <stdio.h>

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

int LIS(int arr[], int n) {
    int dp[n], max_len = 0;
    for (int i = 0; i < n; i++) {
        dp[i] = 1;
        for (int j = 0; j < i; j++) {
            if (arr[i] > arr[j]) {
                dp[i] = max(dp[i], dp[j] + 1);
            }
        }
        max_len = max(max_len, dp[i]);
    }
    return max_len;
}

int main() {
    int arr[] = {10, 22, 9, 33, 21, 50, 41, 60};
    int n = sizeof(arr) / sizeof(arr[0]);
    printf("Length of LIS is %d\n", LIS(arr, n));
    return 0;
}

以上代码中，使用一个数组 `dp` 记录以 `arr[i]` 结尾的递增子序列的最大长度。初始时，每个元素的最大长度为 1。从 `i = 1` 开始，对于每个 `i`，我们在 `0 ~ i-1` 的范围内遍历，如果发现 `arr[i]` 大于 `arr[j]`，则更新 `dp[i]` 为 `dp[j] + 1`，表示在原来的递增子序列基础上增加了一个元素。最后遍历 `dp` 数组，找到其中最大的值即可。