书籍简介
第一章 字符串
1.0 本章导读
1.1 旋转字符串
1.2 字符串包含
1.3 字符串转换成整数
1.4 回文判断
1.5 最长回文子串
1.6 字符串的全排列
1.10 本章习题
第二章 数组
2.0 本章导读
2.1 寻找最小的 k 个数
2.2 寻找和为定值的两个数
2.3 寻找和为定值的多个数
2.4 最大连续子数组和
2.5 跳台阶
2.6 奇偶排序
2.7 荷兰国旗
2.8 矩阵相乘
2.9 完美洗牌
2.10 K个最小和 (UVA 11997 K Smallest Sums)
2.15 本章习题
第三章 树
3.0 本章导读
3.1 红黑树
3.2 B树
3.3 最近公共祖先LCA
3.5 R树：处理空间存储问题
3.10 本章习题
第四章 查找匹配
4.1 有序数组的查找
4.2 行列递增矩阵的查找
4.3 出现次数超过一半的数字
第五章 动态规划
5.0 本章导读
5.1 最大连续乘积子串
5.2 字符串编辑距离
5.3 格子取数
5.4 交替字符串
5.6 最长递增子序列
5.10 本章习题
第六章 海量数据处理
6.0 本章导读
6.1 关联式容器
6.2 分而治之
6.3 simhash算法
6.4 外排序
6.5 MapReduce
6.6 多层划分
6.7 Bitmap
6.8 Bloom filter
6.9 Trie树
6.10 数据库
6.11 倒排索引
6.15 本章习题
第七章 机器学习
7.1 K 近邻算法
7.2 支持向量机
附录 更多题型
附录A 语言基础
附录B 概率统计
附录C 智力逻辑
附录D 系统设计
附录E 操作系统
附录F 网络协议
5.6 最长递增子序列 - 《程序员编程艺术：面试和算法心得》 - IT书包
网站首页
5.6 最长递增子序列
### 题目描述 给定一个长度为N的数组a0,a1,a2...,an-1，找出一个最长的单调递增子序列（注：递增的意思是对于任意的i<j，都满足ai<aj，此外子序列的意思是不要求连续，顺序不乱即可）。例如：给定一个长度为6的数组A{5， 6， 7， 1， 2， 8}，则其最长的单调递增子序列为{5，6，7，8}，长度为4。 ### 分析与解法 #### 解法一：转换为最长公共子序列问题 比如原数组为 - A{5， 6， 7， 1， 2， 8}， 当我们对这个数组进行排序后，排序后的数组为： - A‘{1， 2， 5， 6， 7， 8}。 然后想求数组A的最长递增子序列，其实就是求数组A与它的排序数组A‘的最长公共子序列，原因是原数组A的子序列顺序保持不变，而且排序后A‘本身就是递增的，这样，就保证了两序列的最长公共子序列的递增特性。 如此，若想求数组A的最长递增子序列，其实就是求数组A与它的排序数组A‘的最长公共子序列。 #### 解法二：动态规划 想到这个问题不能改变元素各自的相对顺序，所以我们不能排序，在不能排序的情况下，我们考虑下是否能用动态规划解决。 定义dp[i]为以ai为末尾的最长递增子序列的长度，故以ai结尾的递增子序列 - 要么是只包含ai的子序列 - 要么是在满足j<i并且aj<ai的以ai为结尾的递增子序列末尾，追加上ai后得到的子序列 如此，便可建立递推关系，在O(N^2)时间内解决这个问题。参考代码如下： ```c int n; int a[n]; int dp[n]; void lis() { int res = 0; int i; for (i = 0; i < n; i++) { dp[i] = (dp[i] > dp[i + 1] )? dp[i]:dp[i + 1]; } res = (res > dp[i])?res:dp[i]; printf("%d\n,res"); } ```
上一篇：
5.4 交替字符串
下一篇：
5.10 本章习题
