设L = <a1,a2,...an>是n个不同的实数的序列,L的递增子序列是这样一个子序列:
Lin = <ak1, ak2, ..., akm>, 其中k1 < k2 < ... < km且ak1 < ak2 < ... < akm。
求最大的m,即求最长递增子序列的长度。
使用动态规划解决:
令f[i] 表示长度为i的递增子序列中末尾的元素
len[i] 表示a[1]...a[i]的最长递增子序列的长度
那么如何求len[i]呢?
找出max{j, f[j] < a[i], j = 1...len[i-1] }, 若所有f[j] >= a[i],则令j = 0,
然后len[i] = j+1; 更新f[len[i]] = a[i], 由于f[i]是递增的,所以求
max{j, f[j] < a[i], j = 1...len[i] }时可以用二分查找,整个过程算法复杂度为O(n*logn)
#include <stdio.h>
#include <string.h>
#define DEBUG
#ifdef DEBUG
#define debug(...) printf( __VA_ARGS__)
#else
#define debug(...)
#endif
#define N 20
#define max(a,b) (a) > (b) ? (a) : (b)
int f[N];
void find(int *a, int n)
{
int i, s, t, m, len;
f[1] = a[1];
len = 1;
for (i = 2; i <= n; i++) {
s = 1; t = len;
while (s <= t) {
m = (s+t)/2;
if (f[m] < a[i]) {
s = m+1;
}
else {
t = m-1;
}
}
f[t+1] = a[i];
printf("f[%d] = %d\n", t+1, f[t+1]);
len = max(t+1, len);
}
printf("%d\n", len);
}
int main()
{
int a[] = {0,7,8,3,2,1,1};
find(a,6);
return 0;
}
分享到:
相关推荐
最长递增子序列(Longest Increasing Subsequence, LIS)问题是计算机科学中的一种经典动态规划问题,广泛应用于算法设计和分析。在给定的整数序列中,我们的目标是找到一个尽可能长的、不降序的子序列。这个子序列...
这是我这两天才完成的原创代码,就是比较经典的求一个随机序列的最长递增子序列问题。例如: n=5 随机序列为 5 1 4 2 3,正确输出为1 2 3,即长度为3的递增子序列。里面附带实验详细说明,感兴趣的可以下来参考。 ...
### 最长递增子序列的概念 在探讨最长递增子序列之前,我们首先明确几个基本概念。 #### 定义: 给定一个序列 \( L = \langle a_1, a_2, \ldots, a_n \rangle \),该序列由 \( n \) 个不同的实数组成。最长递增子...
求解最大子序列、最长递增子序列、最长公共子串、最长公共子序列. http://blog.csdn.net/ssuchange/article/details/17341693
最长递增子序列(Longest Increasing Subsequence, LIS)是计算机科学中常见的算法问题,它在数组或序列中寻找一个尽可能长的严格递增子序列。这个问题在多种领域都有应用,比如股票交易策略、生物信息学等。在这个...
在本实验中,我们将探讨如何使用Java编程语言解决“最长递增子序列”(Longest Increasing Subsequence, LIS)的问题。这是一个经典的动态规划问题,在计算机科学和算法设计中具有广泛的应用,例如在股票交易策略、...
最长递增子序列(Longest Increasing Subsequence, LCS)是计算机科学中一种经典的动态规划问题,常见于算法和数据结构的学习。在这个问题中,我们给定一个无序整数序列,目标是找到序列中的一个子序列,使得这个子...
动态规划最长递增子序列 已经实现 请大家赐教
在本实验中,我们关注的是“最长递增子序列”(Longest Increasing Subsequence, LIS)这一经典问题,它是算法课程中的一个核心课题,尤其在动态规划的应用上有着重要的地位。中科大软件学院的这个实验旨在让学生...
本实验涵盖了几个重要的算法概念,包括整数划分、排序算法、最长递增子序列以及幻方矩阵。下面将逐一详细介绍这些知识点。 1. 整数划分: 整数划分是一个数学问题,它涉及将一个正整数n划分为若干个正整数的和,...
在中科大软件学院开设的算法导论课程实验中,要求学生研究和实现最长递增子序列问题。最长递增子序列(Longest Increasing Subsequence,简称LIS)问题是一个经典的计算机科学问题,其目标是在一个无序的整数序列中...
最长递增子序列(Longest Increasing Subsequence, LIS)是计算机科学中一种经典的动态规划问题,广泛应用于算法竞赛和实际编程场景。在这个Java实现中,我们将深入探讨如何找到一个序列中长度最长的递增子序列。 ...
最长递增子序列问题是一个很基本、较常见的小问题,但这个问题的求解方法却并不那么显而易见,需要较深入的思考和较好的算法素养才能得出良好的算法。由于这个问题能运用学过的基本的算法分析和设计的方法与思想,...
标题中的“排序最长递增子序列红黑树”是指在数据结构和算法领域中的两个重要概念:排序和最长递增子序列(Longest Increasing Subsequence, LIS),以及它们与红黑树(Red-Black Tree)的关联。在这个场景中,我们...
最长递增子序列(Longest Increasing Subsequence, LIS)是计算机科学中一个经典的算法问题,主要涉及到了排序、数组处理和优化策略等概念。在这个场景中,我们将关注使用贪心算法和动态规划来解决这个问题,并结合...
### 动态规划:最长单调递增子序列 在计算机科学和算法设计中,动态规划是一种重要的技术,用于解决优化问题。本篇文章将详细介绍如何利用动态规划求解一个经典问题——寻找给定序列中的最长单调递增子序列...
最长递增子序列(Longest Increasing Subsequence, LIS)问题是一个经典的计算机科学问题,它在动态规划、算法设计和序列分析等领域都有广泛的应用。在这个C程序中,我们将深入探讨如何利用C语言来解决这个问题。 ...
最长递增子序列(Longest Increasing Subsequence, LIS)是计算机科学中的一种经典算法问题,主要出现在算法设计与分析的课程中。这个问题的目标是从给定的一组整数中找到一个尽可能长的严格递增的子序列。在本例中...