最长递增子序列问题（Longest Increasing Subsequence），动态规划法解决，贪心算法 + 二分查找优化

---

---

---

问题描述：在一个大小乱序的数列中，找到一个最大长度的递增子序列，子序列中的数据在原始数列中的相对位置保持不变，可以不连续，但必须递增。

输入描述：

第一行输入数列的长度 n。(1 <= n <= 200)
第二行输入数列的数据：a1 a2 a3 ... ... ，每个数据之间用空格隔开。(1 <= ai <= 350)

输出：

输出最大递增子序列的长度。

示例：

输入：
6
2 5 1 5 4 5

输出：
3

说明：
最大递增子序列可以是 {2,4,5} 也可以是 {1,4,5}，所以最大递增子序列的长度为 3.
输出 3

动态规划法

可以使用 动态规划 的思想来设计该算法。定义数组 dp[n]，dp[i] 表示以第 i 个元素结尾的最长递增子序列的长度。（有关动态规划，参考往期文章 【一篇小短文，理解动态规划问题 DP (Dynamic Programming)】）

两个 for 循环嵌套，外层循环遍历数组中的第 i 个元素，内层循环遍历第 i 个元素之前的所有元素。

每次内层循环结束，则计算出当前 第 i 个元素结尾的最长递增子序列长度。

后面的每次循环都基于前面已经解决的子问题。

状态转移方程：

• arr 是长度为 n 的数组，arr[i] 表示第 i 个元素。
• dp[i] 为以 arr[i] 结尾的最长递增子序列的长度。

对于每个元素 arr[i]，它的递增子序列可以通过之前的元素 arr[0], arr[1], ..., arr[i-1] 来扩展，因此我们可以利用之前的状态来更新 dp[i]。

转移方程为：

$$dp[i]=\max (dp[i],dp[j]+1)\text{for}0\le j<i\text{and}arr[i]>arr[j]$$

即，对于每个 i，我们检查所有 j （j 小于 i），如果 arr[i] 大于 arr[j]，那么 arr[i] 可以作为以 arr[j] 结尾的递增子序列的后继，从而更新 dp[i]。

C语言代码实现：

#include <stdio.h>
#include <stdlib.h>int main() {int n;scanf("%d", &n);   // 接收数据 nint *arr = (int*)malloc(sizeof(int) * n); // 动态申请 n 个 int 型数据，数组 arr[n]int *dp = (int*)malloc(sizeof(int) * n);  // 动态申请数组 dp[n]for (int i = 0; i < n; i++) {scanf("%d", (arr + i));    //接收数组数据*(dp + i) = 1;      //初始化 dp 数组，即每个 arr[i] 结尾的数据至少可以形成一个以自身为结尾的递增子序列，长度为1}//进行动态规划for (int i = 1; i < n; i++) {for (int j = 0; j < i; j++) {if (arr[i] > arr[j]) {dp[i] = dp[i] > dp[j] + 1 ? dp[i] : dp[j] + 1;}}}int maxlength = 1;for (int i = 0; i < n; i++) {     //遍历 dp[i] 找到最大的一个if (dp[i] > maxlength)maxlength = dp[i];}printf("%d", maxlength);    //输出最大递增子序列的长度。free(arr);   // 释放 arr 内存free(dp);return 0;
}

如果 arr[i] > arr[j]，则可以构成以递增关系，dp[j] 保存的是以 arr[j] 结尾的最大递增子序列的长度。dp[j] + 1 是因为当前找到的第 i 个元素也被算进来。dp[i] = dp[i] > dp[j] + 1 ? dp[i] : dp[j] + 1; 条件运算符，选择较大的一个更新 dp[i] 的值。

---

---

以输入的数据 4 3 1 2 5 6 为例，代码的执行过程：

1. 外层循环 i = 1：

• arr[1] = 3 查看 i前面的元素：

  • j = 0，arr[0] = 4，因为 arr[1] (3) 小于 arr[0] (4)，无法构成递增子序列，所以 dp[1] 保持为 1。

dp = [1, 1, 1, 1, 1, 1]

2. 外层循环 i = 2：

• arr[2] = 1 查看 i 前面的元素：

  • j = 0，arr[0] = 4，arr[2] (1) 小于 arr[0] (4)，无法构成递增子序列，dp[2] 保持为 1。
  • j = 1，arr[1] = 3，arr[2] (1) 小于 arr[1] (3)，无法构成递增子序列，dp[2] 保持为 1。

dp = [1, 1, 1, 1, 1, 1]

3. 外层循环 i = 3：

• arr[3] = 2 查看 i 前面的元素：

  • j = 0，arr[0] = 4，arr[3] (2) 小于 arr[0] (4)，无法构成递增子序列，dp[3] 保持为 1。
  • j = 1，arr[1] = 3，arr[3] (2) 小于 arr[1] (3)，无法构成递增子序列，dp[3] 保持为 1。
  • j = 2，arr[2] = 1，arr[3] (2) 大于 arr[2] (1)，我们可以在 arr[2] 后面加上 arr[3]，更新 dp[3] = dp[2] + 1 = 2。

dp = [1, 1, 1, 2, 1, 1]

4. 外层循环 i = 4：

• arr[4] = 5 查看 i 前面的元素：

  • j = 0，arr[0] = 4，arr[4] (5) 大于 arr[0] (4)，我们可以在 arr[0] 后面加上 arr[4]，更新 dp[4] = dp[0] + 1 = 2。
  • j = 1，arr[1] = 3，arr[4] (5) 大于 arr[1] (3)，我们可以在 arr[1] 后面加上 arr[4]，更新 dp[4] = dp[1] + 1 = 2（不需要更新，dp[4] 仍然为 2）。
  • j = 2，arr[2] = 1，arr[4] (5) 大于 arr[2] (1)，我们可以在 arr[2] 后面加上 arr[4]，更新 dp[4] = dp[2] + 1 = 2（不需要更新，dp[4] 仍然为 2）。
  • j = 3，arr[3] = 2，arr[4] (5) 大于 arr[3] (2)，我们可以在 arr[3] 后面加上 arr[4]，更新 dp[4] = dp[3] + 1 = 3。

dp = [1, 1, 1, 2, 3, 1]

5. 外层循环 i = 5：

• arr[5] = 6 查看 i 前面的元素：

  • j = 0，arr[0] = 4，arr[5] (6) 大于 arr[0] (4)，我们可以在 arr[0] 后面加上 arr[5]，更新 dp[5] = dp[0] + 1 = 2。
  • j = 1，arr[1] = 3，arr[5] (6) 大于 arr[1] (3)，我们可以在 arr[1] 后面加上 arr[5]，更新 dp[5] = dp[1] + 1 = 2（不需要更新，dp[5] 仍然为 2）。
  • j = 2，arr[2] = 1，arr[5] (6) 大于 arr[2] (1)，我们可以在 arr[2] 后面加上 arr[5]，更新 dp[5] = dp[2] + 1 = 2（不需要更新，dp[5] 仍然为 2）。
  • j = 3，arr[3] = 2，arr[5] (6) 大于 arr[3] (2)，我们可以在 arr[3] 后面加上 arr[5]，更新 dp[5] = dp[3] + 1 = 3。
  • j = 4，arr[4] = 5，arr[5] (6) 大于 arr[4] (5)，我们可以在 arr[4] 后面加上 arr[5]，更新 dp[5] = dp[4] + 1 = 4。

dp = [1, 1, 1, 2, 3, 4]

最终结果：

• 最终 dp 数组为 [1, 1, 1, 2, 3, 4]，表示每个位置上以该元素为结尾的最长递增子序列的长度。
• 最长递增子序列的长度是 4，即 dp 数组中的最大值。

---

---

使用动态规划方法解决该问题，由于使用了双层 for 循环嵌套，所以代码的时间复杂度为 $\text{O}(n^2)$，适用于中小规模数据。

贪心算法 + 二分查找

贪心算法（Greedy Algorithm） 是一种在求解问题时采取局部最优解的策略，目的是通过一步一步地做出选择，期望通过局部最优选择达到全局最优。换句话说，贪心算法在每一步都选择当前看起来最好的（最优的）选项，而不考虑这些选择是否会影响到后续的决策。

贪心算法的特点：

1. 局部最优选择：每次决策时，选择当前最优解，假设局部最优能够带来全局最优解。
2. 不回溯：一旦作出选择，就不会改变或回头考虑先前的选择。贪心算法通常不需要回溯到前一步的决策。
3. 无法保证全局最优解：贪心算法的一个缺点是它并不总是能找到全局最优解，因为局部最优并不意味着全局最优。但是，对于某些问题，贪心算法能够给出全局最优解。

贪心算法工作步骤：

4. 选择：在当前状态下做出一个选择，使得该选择是局部最优的。
5. 可行性检查：检查当前的选择是否符合问题的约束。
6. 解决子问题：做出选择后，递归地解决问题的子问题。
7. 结束条件：当没有更多的选择可做时，结束算法。

C语言实现：

#include <stdio.h>
#include <stdlib.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 - 1;}}return left;
}int main() {int n;scanf("%d", &n);int* arr = (int*)malloc(n * sizeof(int));int index = 0;while (scanf("%d", (arr + index++)) != EOF);// tails 数组，表示递增子序列的尾部元素int* tails = (int*)malloc(n * sizeof(int));int size = 0;  // 记录递增子序列的长度// 贪心 + 二分查找for (int i = 0; i < n; i++) {int pos = binarySearch(tails, size, arr[i]);tails[pos] = arr[i];  // 更新尾部元素if (pos == size) {size++;  // 如果当前位置是尾部的最末位置，子序列的长度加1}}printf("%d\n", size);  // 输出最长递增子序列的长度free(arr);free(tails);return 0;
}

代码解释：

	// 输入部分int n;scanf("%d", &n);int* arr = (int*)malloc(n * sizeof(int));   //申请数组内存int index = 0;while (scanf("%d", (arr + index++)) != EOF);     //使用指针操纵数组 arr ，一直读到 End Of File (EOF)

初始化 tails 数组：

int* tails = (int*)malloc(n * sizeof(int));
int size = 0;  // 记录递增子序列的长度

tails 数组用来存储当前所有递增子序列的尾部元素。在开始时，我们的递增子序列长度为 0，因此 size 初始为 0。

二分查找函数：

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) {  // 如果 mid 位置的元素小于 targetleft = mid + 1;  // 说明 target 可能在 mid 右边，所以更新左边界} else {  // 如果 mid 位置的元素大于或等于 targetright = mid - 1;  // 说明 target 可能在 mid 左边，所以更新右边界}}return left;  // 返回插入位置
}

通过二分查找在一个有序的数组 tails 中找到一个位置，使得如果插入 target，数组依然保持有序。函数的返回值是 target 应该插入的位置。

二分查找的基本思想是：通过反复折半查找范围来逐渐缩小搜索区间，从而提高查找效率。

• binarySearch(int *tails, int size, int target) 二分查找函数，目的是找到 tails 中第一个大于或等于 target 的位置。
• tails[mid] < target 时，表示 target 可以放到 mid 右边，因此我们将 left 移动到 mid + 1。
• tails[mid] >= target 时，表示我们要寻找更小的值，因此将 right 移动到 mid - 1。
• 最终返回的 left 就是 target 应该插入的位置。

遍历数组并更新 tails 数组：

for (int i = 0; i < n; i++) {int pos = binarySearch(tails, size, arr[i]);tails[pos] = arr[i];  // 更新尾部元素if (pos == size) {size++;  // 如果当前位置是尾部的最末位置，子序列的长度加1}
}

• 对于每个输入数组 arr[i]，我们通过二分查找找出它应该插入 tails 数组的位置 pos。
• 如果 tails[pos] 是该元素，说明我们已经可以更新该位置的尾部元素，否则我们在 tails 数组中找到一个位置并将其更新为 arr[i]。
• 如果 pos 等于当前 tails 数组的长度（即 size），意味着我们发现了一个比当前 tails 数组中的任何尾部元素都要大的元素，此时可以将 tails 数组的长度加 1，表示找到了一个新的递增子序列的末尾。

算法的核心思想

1. 贪心算法：
   • 我们试图尽可能让每个新元素扩展已有的递增子序列，或者替换掉某个尾部元素，以便为后续的更大的元素腾出空间。
   • 通过不断更新 tails 数组，我们能确保 tails 数组中保持着当前所有递增子序列的最小尾部元素。这样，tails 数组越长，代表最长递增子序列的长度越长。
2. 二分查找：
   • 我们用二分查找来快速找到 tails 数组中第一个大于或等于当前元素的位置。这是该算法的关键，利用二分查找来确保每次更新 tails 数组的时间复杂度为 O(log n)，从而把总的时间复杂度降到了 O(n log n)。

例子分析

假设输入序列为：4, 3, 1, 2, 5, 6

• 初始化：
  • arr = [4, 3, 1, 2, 5, 6]
  • tails = []，size = 0
• 第 1 个元素 4：
  • binarySearch(tails, 0, 4) 返回位置 0（tails 为空，4 应该放到第一个位置）。
  • 更新 tails = [4]，size = 1。
• 第 2 个元素 3：
  • binarySearch(tails, 1, 3) 返回位置 0（tails[0] = 4，3 比它小，插入位置是 0）。
  • 更新 tails = [3]，size = 1。
• 第 3 个元素 1：
  • binarySearch(tails, 1, 1) 返回位置 0（tails[0] = 3，1 比它小，插入位置是 0）。
  • 更新 tails = [1]，size = 1。
• 第 4 个元素 2：
  • binarySearch(tails, 1, 2) 返回位置 1（tails[0] = 1，2 比它大，插入位置是 1）。
  • 更新 tails = [1, 2]，size = 2。
• 第 5 个元素 5：
  • binarySearch(tails, 2, 5) 返回位置 2（tails[0] = 1，tails[1] = 2，5 比它们都大，插入位置是 2）。
  • 更新 tails = [1, 2, 5]，size = 3。
• 第 6 个元素 6：
  • binarySearch(tails, 3, 6) 返回位置 3（tails[0] = 1，tails[1] = 2，tails[2] = 5，6 比它们都大，插入位置是 3）。
  • 更新 tails = [1, 2, 5, 6]，size = 4。

最后，tails = [1, 2, 5, 6]，最长递增子序列的长度是 4。

---

第二个算法的时间复杂度为 $\text{O}(n\cdot \text{log}n)$ ，适用于大规模数据。在输出最大递增子序列的长度的同时，也找出了具体的最大递增子序列 tails 。

---

---

---

END