求最长单调递增子序列的代码 c语言

在C语言中，求解给定整数数组中最长的单调递增子序列（Longest Increasing Subsequence, LIS）通常可以使用动态规划的方法，例如著名的Kadane算法。下面是一个简单的示例代码：

#include <stdio.h>
#include <stdlib.h>

int lis(int arr[], int n) {
    if (n == 0) return 0;
    
    int dp[n], max_len = 1; // 初始化动态规划数组和最长长度为1
    dp[0] = 1; // 第一个元素本身就是单调递增子序列

    for (int i = 1; i < n; i++) {
        dp[i] = 1; // 假设当前元素单独作为子序列
        for (int j = 0; j < i; j++) {
            if (arr[j] < arr[i]) {
                dp[i] = MAX(dp[i], dp[j] + 1); // 如果前缀和大于已知的最短LIS，更新dp[i]
            }
        }
        max_len = MAX(max_len, dp[i]); // 更新最长子序列长度
    }

    return max_len;
}

// 定义一个MAX函数，用于返回两个整数的最大值
#define MAX(a, b) ((a) > (b) ? (a) : (b))

int main() {
    int arr[] = {10, 9, 2, 5, 3, 7, 101, 18};
    int n = sizeof(arr) / sizeof(arr[0]);
    printf("Length of the longest increasing subsequence is: %d\n", lis(arr, n));
    return 0;
}

这个程序首先初始化每个位置的最长递增子序列长度为1（因为单个元素也是递增），然后遍历数组，对于每个元素，检查所有之前的位置，如果找到一个比它小但是其子序列长度加1更大的值，就更新该元素的DP值。最后返回整个数组中最大DP值，即为最长单调递增子序列的长度。