设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;
}
分享到:
相关推荐
这是我这两天才完成的原创代码,就是比较经典的求一个随机序列的最长递增子序列问题。例如: n=5 随机序列为 5 1 4 2 3,正确输出为1 2 3,即长度为3的递增子序列。里面附带实验详细说明,感兴趣的可以下来参考。 ...
求一个由n个整数组成的整数序列的最长递增子序列。一个整数序列的递增子序列可以是序列中非连续的数按照原序列顺序排列而成的。 最长递增子序列是其递增子序列中长度最长的。
求解最大子序列、最长递增子序列、最长公共子串、最长公共子序列. http://blog.csdn.net/ssuchange/article/details/17341693
动态规划最长递增子序列 已经实现 请大家赐教
最长子序列 什么是最长递增子序列呢? 问题描述如下: 设L=,a2,…,an>是n个不同的实数的序列,L的递增子序列是这样一个子序列Lin=,ak2,…,akm>,其中k1…且aK1…。求最大的m值
最长递增子序列LCS的实现C源码,大学算法导论课程实验
中科大软件学院 算法导论课程实验 正式题目二 最长递增子序列 Visual Studio 2012 项目包 使用4种不同的方法实现最长递增子序列
最长递增子序列问题是一个很基本、较常见的小问题,但这个问题的求解方法却并不那么显而易见,需要较深入的思考和较好的算法素养才能得出良好的算法。由于这个问题能运用学过的基本的算法分析和设计的方法与思想,...
算法课实验代码,包括整数划分、各类排序、最长递增子序列、幻方矩阵等试验
贪心算法、动态规划实现最长递增子序列的求取(MFC编程)。
动态规划:最长单调递增子序列 A numeric sequence of ai is ordered if a1 (a1, a2, ..., aN) be any sequence (ai1, ai2, ..., aiK), where 1 , sequence (1, 7, 3, 5, 9, 4, 8) has ordered subsequences, e. ...
中科大软件学院 算法导论课程实验 正式题目二 最长递增子序列 实验报告 使用4种不同的方式实现最长递增子序列
中国科学技术大学软件学院《算法设计与分析》实验题目四
给你一个整数数组 nums ,找到...解释:最长递增子序列是 [2,3,7,101],因此长度为 4 。 示例 2: 输入:nums = [0,1,0,3,2,3] 输出:4 示例 3: 输入:nums = [7,7,7,7,7,7,7] 输出:1 参数范围: 1 -104 [i] <=104
最长递增子序列的另外一种C语言实现代码,大学算法导论课程实验
C++的课程作业,一个简单的程序,用dev就能直接运行,老师应该不会太仔细检查,糊弄一下肯定没事的,不过最好能自己看懂就是了
包括排序 最长递增子序列 红黑树三个相关程序
这是递增子序列的java实现版 希望对大家有所启迪