最长上升子序列算法导论c语言

最长上升子序列 (Longest Increasing Subsequence, LIS) 算法是一种经典的动态规划问题，用于找出数组中最长的按顺序递增的元素序列。在 C 语言中，你可以使用动态规划的思想来解决这个问题。以下是基本步骤：

1. 初始化：创建一个数组 `dp`，长度与输入数组相同，所有元素初始化为 1。这是因为每个数字本身就是其自身的最长上升子序列。

2. 动态计算：遍历输入数组，对于每个元素 `arr[i]`，检查从 0 到 i - 1 的范围内是否存在一个比它小且 `dp[j] + 1` （`j` 是前一个元素的位置）更大的值。如果存在，更新 `dp[i]` 为这个较大的值。

3. 记录过程：同时，在遍历过程中，找到并维护最长上升子序列的长度，这将是最终的答案。

4. 返回结果：遍历结束后，`dp` 数组的最后一个非零元素即为最长上升子序列的长度。若需要实际的子序列，可以根据 `dp` 数组构建。

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

int longest_increasing_subsequence(int arr[], int n) {
    int dp[n];
    for (int i = 0; i < n; i++) {
        dp[i] = 1;
    }

    for (int i = 1; i < n; i++) {
        for (int j = 0; j < i; j++) {
            if (arr[i] > arr[j] && dp[i] < dp[j] + 1) {
                dp[i] = dp[j] + 1;
            }
        }
    }

    return *max_element(dp, dp+n);
}

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", longest_increasing_subsequence(arr, n));
    return 0;
}