C语言实现最长递增子序列（LIS）算法详解

问题描述

最长递增子序列（Longest Increasing Subsequence, LIS）是经典的算法问题。要求在一个无序的整数序列中，找到一个子序列，使得该子序列中的元素严格递增，并且其长度在所有可能的递增子序列中是最长的。

示例：

• 输入： 1 3 7 5
• 输出： 3 （对应的子序列为 1, 3, 5 或 1, 3, 7）

算法解决思路：动态规划

为了高效求解此问题，我们采用动态规划（Dynamic Programming）的方法。核心定义如下：

1. 状态定义： 设 lgs[i] 表示以序列中第 i 个元素（即索引 i）结尾的最长递增子序列的长度。
2. 初始状态： 每个元素自身至少构成一个长度为 1 的递增子序列，因此初始化所有 lgs[i] = 1。
3. 状态转移： 对于每一个位置 i，我们需要遍历它之前的所有位置 j（0 ≤ j < i）。如果 data[i] > data[j]，说明可以将 data[i] 接在以 data[j] 结尾的递增子序列之后。此时，以 i 结尾的新子序列长度为 lgs[j] + 1。我们需要取所有满足条件的 j 中最大的那个值作为 lgs[i] 的值。
4. 最终结果： 遍历结束后，lgs 数组中的最大值即为整个序列的最长递增子序列长度。

C语言实现代码

以下是具体的C语言实现。代码包含了数组输入、动态规划计算以及最大值的提取过程。

#include "stdio.h"
#include "stdlib.h"

#define MAXDATA 10000

int main(){
    int data[MAXDATA];   /* 存储输入的数据序列 */
    int lgs[MAXDATA];    /* 记录以每个点为右端时的最长子序列长度 */
    int n, temp, k;      /* n: 序列长度, temp: 中间变量用于比较 */
    
    /* 1. 读取序列长度 */
    scanf("%d", &n);
    
    /* 2. 边界检查 */
    if(n > 10000){
        return 0;         
    }
    
    /* 3. 读取序列数据 */
    for(int i=0; i<n; i++){
        scanf("%d", &data[i]);
    }
    
    /* 4. 初始化 DP 数组，每个位置初始长度为 1 */
    for(int i=0; i<n; i++){
        lgs[i] = 1;
    }
    
    /* 5. 核心动态规划逻辑 */
    for(int i=1; i<n; i++){
        temp = 1;
        /* 与前面的每一个元素进行比较 */
        for(int j=0; j<i; j++){ 
            /* 如果当前数据比前面的某一个值大 */
            if(data[i] > data[j]){ 
                /* 找出该点能获得的最大子序列长度 */
                /* 注意：原逻辑中 lgs[i]+lgs[j] 其实应理解为 max(lgs[i], lgs[j]+1) */
                /* 由于初始化为1且temp从1开始，这里实际是在累积寻找最大值 */
                if(lgs[j] + 1 > temp){ 
                    temp = lgs[j] + 1;
                } 
            }
        }
        lgs[i] = temp;
    }
    
    /* 6. 找出所有 lgs[i] 中的最大值 */
    temp = lgs[0];
    for(int i=1; i<n; i++){
        if(lgs[i] > temp){
            temp = lgs[i];
        }
    }
    
    /* 7. 输出结果 */
    printf("%d", temp);
    system("pause");
    return 0;
}

代码关键点说明：

• 内存限制： 定义了一个常量 MAXDATA 10000，适用于长度不超过1万的数据序列。若需处理更大规模数据，建议改用动态内存分配（如 malloc）。
• 时间复杂度： 使用了双重循环，外层遍历每个元素，内层遍历前驱元素，因此时间复杂度为 O(N^2)。对于 N < 10000 的场景表现良好；若 N 达到 10^5 级别，通常需优化为 O(N log N) 的贪心+二分查找算法。
• 输入格式： 程序首先读取一个整数 n 代表序列长度，随后连续读取 n 个整数。

总结

上述方法通过建立 lgs 数组保存中间计算结果，避免了重复计算，清晰直观地解决了最长递增子序列问题。理解状态转移方程 lgs[i] = max(lgs[j] + 1) 是掌握此类动态规划问题的关键。 以上就是C语言实现最长递增子序列（LIS）问题的详细内容，更多关于C语言算法设计与动态规划的资料请关注本站其它相关文章！