C语言实现最长递增子序列算法

简介

最长递增子序列（Longest Increasing Subsequence，LIS）问题是在一个给定的整数序列中，找到一个子序列，使得这个子序列中的元素是递增的，并且这个子序列的长度是所有递增子序列中最长的。这是一个经典的动态规划问题，在计算机科学和算法设计中有广泛的应用，例如在数据分析、生物信息学等领域。

基础概念
- 子序列的定义
- 最长递增子序列的定义
使用方法
- 动态规划方法
- 贪心 + 二分查找方法
常见实践
- 数组中的最长递增子序列
- 应用场景举例
最佳实践
- 代码优化
- 时间复杂度和空间复杂度分析
代码示例
- 动态规划实现
- 贪心 + 二分查找实现
小结
参考资料

基础概念

子序列的定义

子序列是从一个序列中通过删除一些元素（也可以不删除任何元素）但不改变剩余元素的顺序而得到的新序列。例如，对于序列 [1, 3, 4, 2, 5]，[1, 3, 4]、[1, 2, 5] 都是它的子序列。

最长递增子序列的定义

最长递增子序列是在一个给定序列中，找到一个长度最长的子序列，并且这个子序列中的元素是严格递增的。例如，对于序列 [10, 9, 2, 5, 3, 7, 101, 18]，其最长递增子序列是 [2, 3, 7, 18]，长度为 4。

使用方法

动态规划方法

动态规划是解决最长递增子序列问题的一种常用方法。基本思路是定义一个数组 dp，其中 dp[i] 表示以第 i 个元素结尾的最长递增子序列的长度。状态转移方程为：

[ dp[i] = \max_{0 \leq j < i, a[j] < a[i]}(dp[j]) + 1 ]

具体步骤如下：

初始化 dp 数组，每个元素初始值为 1，因为每个元素自身都可以构成一个长度为 1 的递增子序列。
遍历序列中的每个元素 a[i]。
对于每个 a[i]，遍历其前面的所有元素 a[j]（j < i），如果 a[j] < a[i]，则更新 dp[i] 为 dp[i] 和 dp[j] + 1 中的较大值。
最终，dp 数组中的最大值就是整个序列的最长递增子序列的长度。

贪心 + 二分查找方法

这种方法利用贪心策略和二分查找来降低时间复杂度。基本思路是维护一个数组 tails，tails[i] 表示长度为 i + 1 的递增子序列的末尾元素的最小值。具体步骤如下：

初始化 tails 数组为空。
遍历序列中的每个元素 a[i]。
如果 a[i] 大于 tails 数组中的最后一个元素，则将 a[i] 追加到 tails 数组的末尾。
否则，使用二分查找在 tails 数组中找到第一个大于等于 a[i] 的元素的位置 pos，并将 tails[pos] 更新为 a[i]。
最终，tails 数组的长度就是最长递增子序列的长度。

常见实践

数组中的最长递增子序列

给定一个整数数组，求其最长递增子序列的长度。

应用场景举例

在数据分析中，可以用最长递增子序列算法来分析股票价格的上涨趋势。在生物信息学中，可以用于分析 DNA 序列中的某些模式。

最佳实践

代码优化

在动态规划方法中，可以通过减少不必要的计算来优化代码。在贪心 + 二分查找方法中，可以使用标准库中的二分查找函数来提高代码的可读性和效率。

时间复杂度和空间复杂度分析

动态规划方法的时间复杂度为 ( O(n^2) )，空间复杂度为 ( O(n) )，其中 ( n ) 是序列的长度。
贪心 + 二分查找方法的时间复杂度为 ( O(n \log n) )，空间复杂度为 ( O(n) )。

代码示例

动态规划实现

#include <stdio.h>

int lengthOfLIS(int* nums, int numsSize) {
    if (numsSize == 0) return 0;
    int dp[numsSize];
    for (int i = 0; i < numsSize; i++) {
        dp[i] = 1;
    }
    int maxLen = 1;
    for (int i = 1; i < numsSize; i++) {
        for (int j = 0; j < i; j++) {
            if (nums[i] > nums[j] && dp[i] < dp[j] + 1) {
                dp[i] = dp[j] + 1;
            }
        }
        if (dp[i] > maxLen) {
            maxLen = dp[i];
        }
    }
    return maxLen;
}

int main() {
    int nums[] = {10, 9, 2, 5, 3, 7, 101, 18};
    int numsSize = sizeof(nums) / sizeof(nums[0]);
    int len = lengthOfLIS(nums, numsSize);
    printf("最长递增子序列的长度是: %d\n", len);
    return 0;
}

贪心 + 二分查找实现

#include <stdio.h>
#include <string.h>

// 二分查找函数
int binarySearch(int tails[], int size, int target) {
    int left = 0, right = size - 1;
    while (left < right) {
        int mid = left + (right - left) / 2;
        if (tails[mid] < target) {
            left = mid + 1;
        } else {
            right = mid;
        }
    }
    return left;
}

int lengthOfLIS(int* nums, int numsSize) {
    if (numsSize == 0) return 0;
    int tails[numsSize];
    memset(tails, 0, sizeof(tails));
    int size = 0;
    for (int i = 0; i < numsSize; i++) {
        if (size == 0 || nums[i] > tails[size - 1]) {
            tails[size++] = nums[i];
        } else {
            int pos = binarySearch(tails, size, nums[i]);
            tails[pos] = nums[i];
        }
    }
    return size;
}

int main() {
    int nums[] = {10, 9, 2, 5, 3, 7, 101, 18};
    int numsSize = sizeof(nums) / sizeof(nums[0]);
    int len = lengthOfLIS(nums, numsSize);
    printf("最长递增子序列的长度是: %d\n", len);
    return 0;
}

小结

本文详细介绍了 C 语言实现最长递增子序列算法的基础概念、使用方法、常见实践以及最佳实践。动态规划方法简单直观，但时间复杂度较高；贪心 + 二分查找方法则在时间复杂度上有明显优势。读者可以根据具体的应用场景选择合适的方法来解决问题。

参考资料

《算法导论》
LeetCode 官方文档
各种在线算法教程网站