最长递增子序列
最后更新于：2022-04-01 16:17:36
# 最长递增子序列
[http://blog.csdn.net/lisonglisonglisong/article/details/45241965](http://blog.csdn.net/lisonglisonglisong/article/details/45241965)
最长递增子序列（Longest Increasing Subsequence）是指找到一个给定序列的最长子序列的长度，使得子序列中的所有元素单调递增。
例如：{ 3，5，7，1，2，8 } 的 LIS 是 { 3，5，7，8 }，长度为 4。
### 解法一：转化为求最长公共子序列
其实可以把 求最长递增子序列问题 转化为 求最长公共子序列的问题。
- 设数组 { 3， 5， 7， 1， 2， 8 } 为 A
- 对数组 A 排序，排序后的数组为 B = { 1， 2， 3， 5， 7， 8 }。
- 于是，求数组 A 的最长递增子序列，就是求数组 A 与数组 B 的最长公共子序列。
最长公共子序列的求法见《[动态规划DP](http://blog.csdn.net/lisonglisonglisong/article/details/41548557)》。本方法的时间复杂度是
Θ(nlgn)+Θ(n2)=Θ(n2)
### 解法二：动态规划法
虽然解法一也是使用动态规划，但是与解法一不同的是，解法二不进行转化，而是直接在原问题上采用动态规划法。
**最优子结构：**
对于长度为 N 的数组 A[N]={a0,a1,a2,…,an−1}，假设我们想求以ai 结尾的最大递增子序列长度，设为L[i]，那么
L[i]=⎧⎩⎨max(L[j])+1,1,where j<i and A[j]<A[i]otherwise
也就是 j 的范围是 0 到 i–1。这样，想求ai 结尾的最大递增子序列的长度，我们就需要遍历 i 之前的所有位置 j（0到 i-1），找出A[j]<A[i]，计算这些j 中，能产生最大 L[j] 的 j，之后就可以求出L[i]。之后对每一个A[N]中的元素都计算以他们各自结尾的最大递增子序列的长度，这些长度的最大值，就是我们要求的问题——数组A的最大递增子序列的长度。
**重叠子问题：**
根据上述推导式采用递归实现的话，有些子问题会被计算很多次。
**动态规划法：**
综上所述，LIS 问题具有动态规划需要的两个性质，可以使用动态规划求解该问题。设数组 A = { 3，5，7，1，2，8 }，则：
具体的打表方式如下：
- 初始化对角线为 1；
- 对每一个 i，遍历 j（0 到 i-1）：
- 若`A[i] <= A[j]`，置 1。
- 若`A[i] > A[j]`，取第 j 行的最大值加 1。
打完表以后，最后一行的最大值就是最长递增子序列的长度。由于每次都进行遍历，故时间复杂度还是 Θ(n2)。
[](http://blog.csdn.net/lisonglisonglisong/article/details/45241965)
~~~
// LIS 的动态规划方式实现
#include <iostream>
using namespace std;
int getLISLength(int A[], int len) {
//定义一维数组并初始化为1
int* lis = new int[len];
for (int i = 0; i < len; ++i)
lis[i] = 1;
// 计算每个i对应的lis最大值，即打表的过程
for (int i = 1; i < len; ++i)
for (int j = 0; j < i; ++j) // 0到i-1
if ( A[i] > A[j] && lis[i] < lis[j] + 1)
lis[i] = lis[j] + 1; // 更新
// 数组中最大的那个，就是最长递增子序列的长度
int maxlis = 0;
for (int i = 0; i < len; ++i)
if ( maxlis < lis[i] )
maxlis = lis[i];
delete [] lis;
return maxlis;
}
~~~
### 解法三：Θ(nlgn)的方案
本解法的具体操作如下：
- 建立一个辅助数组array，依次读取数组元素 x 与数组末尾元素 top比较：
- 如果 x > top，将 x 放到数组末尾；
- 如果 x < top，则二分查找数组中第一个 大于等于x 的数，并用 x 替换它。
遍历结束之后，最长递增序列长度即为栈的大小。
注意c数组的下标代表的是子序列的长度，c数组中的值也是按递增顺序排列的。这才可能用二分查找。
数组array[i]存储的是子序列长度为i的序列最后一个值（该值是该子序列中最大的元素；如果长度为i的序列有多个，那么array[i]存放这类序列最后元素中的最小一个）
~~~
int getLISLength(int num[], int length) {
vector<int> ivec;
for (int i = 0; i < length; ++i) {
if (ivec.size() == 0 || ivec.back() < num[i])
ivec.push_back(num[i]);
else {
int low = 0, high = ivec.size() - 1;
while (low < high) {
int mid = (low + high) / 2;
if (ivec[mid] < num[i])
low = mid + 1;
else
high = mid - 1;
}
ivec[low] = num[i];
}
}
return ivec.size();
}
~~~
特别注意的是：本方法只能用于求最长递增子序列的长度，辅助数组中的序列不是最长递增子序列：
-
例一：原序列为1，5，8，3，6，7
辅助数组为1，5，8，此时读到3，用3替换5，得到1，3，8； 再读6，用6替换8，得到1，3，6；再读7，得到最终栈为1，3，6，7。最长递增子序列为长度4。
-
例二：原序列为1，5，8，3
则最栈辅助数组为1，3，8。明显这不是最长递增子序列！
# 合唱队问题
<table id="table1" class="grid grid_tb " border="0" cellpadding="0" cellspacing="0"><tbody><tr><td class="grid_left_td" width="10%">描述: </td><td width="90%"><p style="white-space:normal">计算最少出列多少位同学，使得剩下的同学排成合唱队形</p><p style="white-space:normal">说明：</p><p style="white-space:normal"><span style="font-family:'times new roman'">N位同学站成一排，音乐老师要请其中的(N-K)位同学出列，使得剩下的K位同学排成合唱队形。 <br/>合唱队形是指这样的一种队形：设K位同学从左到右依次编号为1，2…，K，他们的身高分别为T1，T2，…，TK， 则他们的身高满足存在i（1<=i<=K）使得Ti<T2<......<Ti-1<Ti>Ti+1>......>TK。 <br/> 你的任务是，已知所有N位同学的身高，计算最少需要几位同学出列，可以使得剩下的同学排成合唱队形。 <br/></span></p><p style="white-space:normal"> </p><p><br/></p> </td></tr><tr><td class="grid_left_td">知识点:</td><td> 循环 </td></tr><tr><td class="grid_left_td">题目来源:</td><td> 内部整理 </td></tr><tr><td class="grid_left_td">练习阶段:</td><td> 初级 </td></tr><tr><td class="grid_left_td">运行时间限制:</td><td>无限制</td></tr><tr><td class="grid_left_td">内存限制:</td><td>无限制</td></tr><tr><td class="grid_left_td">输入:</td><td> <p style="white-space:normal">整数N</p><p style="white-space:normal">一行整数，空格隔开，N位同学身高</p><p><br/></p> </td></tr><tr><td class="grid_left_td">输出:</td><td> <p><span style="font-family:'times new roman'">最少需要几位同学出列</span><br/></p> </td></tr><tr><td class="grid_left_td">样例输入:</td><td><pre>8
186 186 150 200 160 130 197 200
</pre></td></tr><tr><td class="grid_left_td">样例输出:</td><td><pre>4
</pre></td></tr></tbody></table>
根据题意可知，我们需要求出一个“中间点”，使得其左边的【最长递增子序列】和其右边的【最长递减子序列】之和最大。
~~~
#include <iostream>
#include <vector>
using namespace std;
int LonggestIncreaseLength(vector<int> &vec) {
vector<int> result(vec.size(), 1);
vector<int> result2(vec.size(), 1);
for (int i = 1; i < vec.size(); i++) {
for (int j = 0; j < i; j++) {
if (vec[i] > vec[j] && result[i] < result[j] + 1)
result[i] = result[j] + 1;
}
}
for (int i = vec.size() - 2; i >= 0; --i) {
for (int j = vec.size() - 1; j > i; --j) {
if (vec[i] > vec[j] && result2[i] < result2[j] + 1)
result2[i] = result2[j] + 1;
}
}
int max = 0;
for (int i = 0; i < vec.size(); i++) {
if (max < result[i] + result2[i])
max = result[i] + result2[i];
}
return vec.size() - max + 1;
}
int main() {
int n;
cin >> n;
if (n <= 0)
return 0;
vector<int> ivec(n);
for (int i = 0; i < n; i++)
cin >> ivec[i];
cout << LonggestIncreaseLength(ivec) << endl;
}
~~~