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

ops/2025/1/21 12:29:03/

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

输入描述：

第一行输入数列的长度 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]。

转移方程为：

d p [ i ] = max ⁡ ( d p [ i ] , d p [ j ] + 1 ) for 0 ≤ j < i and a r r [ i ] > a r r [ j ] dp[i] = \max(dp[i], dp[j] + 1) \quad \text{for} \quad 0 \leq j < i \quad \text{and} \quad arr[i] > arr[j] dp[i]=max(dp[i],dp[j]+1)for0≤j<iandarr[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 循环嵌套，所以代码的时间复杂度为 O ( n 2 ) \text{O}(n^2) O(n2)，适用于中小规模数据。

算法>贪心算法 + 二分查找

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

算法>贪心算法的特点：

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

算法>贪心算法工作步骤：

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

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。

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

END


http://www.ppmy.cn/ops/151910.html

相关文章

git创建分支，推送分支，合并分支，回退

git创建分支，推送分支，合并分支，回退

1.可视化操作初始化仓库&#xff0c;设置远程连接&#xff0c;抓取远程仓库的分支内容,然后在版本管理的原创下面的主支 点击重置到哪个版本&#xff0c;覆盖原始内容(取消保持工作区的内容) 2.创建并切换到新分支&#xff1a;git checkout -b lzh (如果是切换不创建去掉-b) 3…
阅读更多...
【数据分享】1929-2024年全球站点的逐年平均气温数据（Shp\Excel\无需转发）

【数据分享】1929-2024年全球站点的逐年平均气温数据（Shp\Excel\无需转发）

气象数据是在各项研究中都经常使用的数据&#xff0c;气象指标包括气温、风速、降水、湿度等指标&#xff0c;其中又以气温指标最为常用&#xff01;说到气温数据&#xff0c;最详细的气温数据是具体到气象监测站点的气温数据&#xff01;本次我们为大家带来的就是具体到气象监…
阅读更多...
无人机技术架构剖析！

无人机技术架构剖析！

一、飞机平台系统 飞机平台系统是无人机飞行的主体平台&#xff0c;主要提供飞行能力和装载功能。它由机体结构、动力装置、电气设备等组成。 机体结构&#xff1a;无人机的机身是其核心结构&#xff0c;承载着其他各个组件并提供稳定性。常见的机身材料包括碳纤维、铝合金、…
阅读更多...
睡眠时间影响因素K-Means可视化分析+XGBoost预测

睡眠时间影响因素K-Means可视化分析+XGBoost预测

1. 导包及数据展示 import numpy as np import pandas as pd import seaborn as sns import matplotlib import matplotlib.pyplot as plt from sklearn.model_selection import train_test_split from sklearn.cluster import KMeans from xgboost import XGBRegressor from …
阅读更多...
【2024 CSDN博客之星】技术洞察类：从DeepSeek-V3的成功，看MoE混合专家网络对深度学习算法领域的影响（MoE代码级实战）

【2024 CSDN博客之星】技术洞察类：从DeepSeek-V3的成功，看MoE混合专家网络对深度学习算法领域的影响（MoE代码级实战）

目录 一、引言 1.1 本篇文章侧重点 1.2 技术洞察—MoE&#xff08;Mixture-of-Experts&#xff0c;混合专家网络&#xff09; 二、MoE&#xff08;Mixture-of-Experts&#xff0c;混合专家网络&#xff09; 2.1 技术原理 2.2 技术优缺点 2.3 业务代码实践 2.3.1 业务场…
阅读更多...
.gitignore配置忽略out目录

.gitignore配置忽略out目录

文章目录 说明操作 说明 可以结合IDEA可视化操作git&#xff0c;只要不删除远程仓库&#xff0c;如果本地操作项目出现错误&#xff0c;可以直接修改远程仓库的.gitignore文件&#xff0c;并重新拉取项目到本地。 操作 在项目根目录下找到 .gitignore 文件&#xff0c;打开并…
阅读更多...
【java数据结构】优先级队列（堆）

【java数据结构】优先级队列（堆）

【java数据结构】优先级队列&#xff08;堆&#xff09; 一、优先级队列1.1 概念 二、优先级队列的模拟实现2.1 堆的概念2.1.1堆的性质 2.2 堆的存储方式2.3 堆的创建2.3.1 向下调整&#xff08;以小堆为例&#xff09;&#xff1a;2.3.2 堆的创建2.3.3 创建堆的时间复杂度 2.4…
阅读更多...
【c++】【算法】【动态规划】最长公共子序列

【c++】【算法】【动态规划】最长公共子序列

【c】【算法】【动态规划】最长公共子序列 //递归方式 //最长公共子序 //直接递归 求最长公共子序长度 int FindValue(const string& X, const string& Y, int i, int j) {if (i 0 || j 0)return 0;if (X[i] Y[j])return FindValue(X, Y, i - 1, j - 1)1;else retu…
阅读更多...
最新文章

Copyright @ 2022~2023