C语言写Longest Ordered Subsequence

在C语言中，Longest Ordered Subsequence (最长递增子序列)是一个常见的动态规划问题。我们可以使用二维数组或者自定义数据结构来解决它。这里是一个简单的解决方案：

#include <stdio.h>

// 定义一个结构体表示元素和它的索引
typedef struct {
    int num;
    int index;
} Node;

// 动态规划函数，lis[i] 存储以 nums[i] 结尾的最长递增子序列长度
int longestIncreasingSubsequence(int arr[], int n) {
    int lis[n];
    // 初始化所有序列长度为1，因为每个数都是其自身的单元素序列
    for (int i = 0; i < n; i++) {
        lis[i] = 1;
    }

    // 遍历数组，比较当前元素与前一个元素
    for (int i = 1; i < n; i++) {
        for (int j = 0; j < i; j++) {
            if (arr[i] > arr[j]) {
                // 如果当前元素大于前一个，尝试将其添加到前者的序列中
                lis[i] = max(lis[i], lis[j] + 1);
            }
        }
    }

    // 找到全局最大值即为最长递增子序列的长度
    int max_len = 0;
    for (int i = 0; i < n; i++) {
        max_len = max(max_len, lis[i]);
    }

    return max_len;
}

// 辅助函数计算两个整数的最大值
int max(int a, int b) {
    return a > b ? a : b;
}

int main() {
    int arr[] = {10, 9, 2, 5, 3, 7, 101, 18};
    int n = sizeof(arr) / sizeof(arr[0]);
    int result = longestIncreasingSubsequence(arr, n);
    printf("Length of the Longest Increasing Subsequence is %d\n", result);

    return 0;
}

在这个代码中，`longestIncreasingSubsequence`函数通过迭代数组并更新每个元素的最长递增子序列长度，最后返回整个序列中最长的一个。