用c语言写一个最长不下降子序列

在 C 语言中，编写一个求解最长不降子序列（Longest Increasing Subsequence，LIS）的问题通常会采用动态规划的方法。这里是一个简单的实现示例：

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

#define MAXN 1000

int lis(int arr[], int n) {
    int dp[MAXN]; // 存储每个元素到其最长上升子序列的长度
    int max_len = 1; // 最长子序列长度初始值为 1 (因为每个元素都是升序)

    // 初始化数组dp，所有元素的初始长度为1
    for (int i = 0; i < n; i++) {
        dp[i] = 1;
    }

    // 遍历数组，更新dp数组
    for (int i = 1; i < n; i++) {
        for (int j = 0; j < i; j++) {
            if (arr[i] > arr[j]) { // 如果当前元素大于之前的元素
                dp[i] = ((dp[i] > dp[j]) ? dp[i] : dp[j]) + 1; // 更新当前元素的长度
                if (dp[i] > max_len) { // 如果新长度比之前最大长度还大
                    max_len = dp[i];
                }
            }
        }
    }

    return max_len;
}

int main() {
    int arr[] = {10, 9, 2, 5, 3, 7, 101, 18};
    int n = sizeof(arr) / sizeof(arr[0]);

    printf("Length of longest increasing subsequence: %d\n", lis(arr, n));

    return 0;
}

这个程序首先初始化一个 `dp` 数组来存储每个元素的最长递增子序列长度。然后，遍历输入数组，对于每个元素，如果它大于前面某个元素，就尝试将其加入到那个元素的 LIS 中，并更新 `dp` 数组。最后返回 `max_len` 即为最长不降子序列的长度。