在本文中，我们将学习如何使用 C 语言来查找给定序列的最长递增子序列（LIS）。LIS 是指一个序列中最长的子序列，且该子序列中的所有元素都按递增顺序排列。
示例：
**输入：**
序列: [10, 22, 9, 33, 21, 50, 41, 60, 80]
**输出：**
最长递增子序列的长度为: 6
!LIS最长递增子序列 LIS
目录
- 方法 1：使用递归
- 方法 2：使用记忆化
- 方法 3：使用动态规划
- 方法 4：使用二分查找
方法 1：使用递归
在这种方法中，我们将探索所有可能的子序列，并选出最长的那个递增子序列。通过递归地将每个元素与其之前的元素进行比较，我们可以决定是否将其包含在子序列中。
方法思路
> – 创建一个函数 INLINECODE07c13e99，接收数组 INLINECODEf2a814b6，其长度 INLINECODEf9bd2393 以及索引 INLINECODE85c7f48e。
> – 基本条件： 如果数组长度为 1，则返回 1。
> – 递归计算以每个索引结尾的 LIS。
> – 将当前元素与前一个元素进行比较，以维持递增顺序，并计算每个元素的 LIS。
> – 返回包含或不包含当前元素所获得的最大长度。
下面是上述方法的实现：
C
CODEBLOCK_9937f266
输出
Length of LIS is 6
时间复杂度： O(2^n)，由于存在重叠子问题的情况（如上文递归树图所示），该递归方法的时间复杂度是指数级的。
辅助空间： O(1)。除了内部栈空间外，没有使用额外的空间来存储数值。
方法 2：使用记忆化
我们可以使用记忆化技术来优化递归方法，它通过存储子问题的结果并在相同输入再次出现时重用它们。这避免了冗余计算，并显著降低了时间复杂度。
方法思路
> – 创建一个数组 memo 来存储每个索引的 LIS。
> – 实现一个函数 INLINECODE84acf6bc，接收 INLINECODE117f29af、INLINECODE7d12e96c 和记忆化数组 INLINECODE5502475c。
> – 基本条件： 如果数组长度为 1，则返回 1。
> – 如果结果已经计算过，则直接返回它。
> – 递归计算并存储剩余元素的结果。
> – 从记忆化数组中返回计算结果。
下面是上述方法的实现：
C
// C program to find longest increasing subsequence using
// Memoization
#include
#include
// Function to return the maximum of two integers
int max(int a, int b) { return (a > b) ? a : b; }
// Function to find the length of the Longest Increasing
// Subsequence (LIS) using memoization
int lisMemoization(int arr[], int n, int* memo)
{
// If the value is already computed, return it
if (memo[n] != -1)
return memo[n];
// Initialize maxendinghere to 1 for the current
// element
int res, maxendingh