最长递增子序列

淡淡的烟草味﹌ 2022-08-08 05:08 237阅读 0赞

# 最长递增子序列 #

[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][DP]》。本方法的时间复杂度是

Θ(*n**l**g**n*)\+Θ(*n*2)=Θ(*n*2)

## 解法二：动态规划法 ##

虽然解法一也是使用动态规划，但是与解法一不同的是，解法二不进行转化，而是直接在原问题上采用动态规划法。

**最优子结构：**

对于长度为 N 的数组 *A*\[*N*\]=\{ *a*0,*a*1,*a*2,…,*a**n*−1\}，假设我们想求以*a**i* 结尾的最大递增子序列长度，设为*L*\[*i*\]，那么

*L*\[*i*\]=⎧⎩⎨*m**a**x*(*L*\[*j*\])\+1,1,where *j*<*i* and *A*\[*j*\]<*A*\[*i*\]otherwise

也就是 *j* 的范围是 0 到 *i*–1。这样，想求*a**i* 结尾的最大递增子序列的长度，我们就需要遍历 *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 \}，则：

![20150424101652021][]

具体的打表方式如下：

* 初始化对角线为 1；
 * 对每一个 i，遍历 j（0 到 i-1）： 
 
 
 * 若`A[i] <= A[j]`，置 1。
 * 若`A[i] > A[j]`，取第 j 行的**最大值**加 1。

打完表以后，最后一行的最大值就是最长递增子序列的长度。由于每次都进行遍历，故**时间复杂度还是 Θ(*n*2)**。

// 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> 
 <tbody> 
 <tr> 
 <td>描述:&nbsp;</td> 
 <td> 计算最少出列多少位同学，使得剩下的同学排成合唱队形 说明： N位同学站成一排，音乐老师要请其中的(N-K)位同学出列，使得剩下的K位同学排成合唱队形。&nbsp; 合唱队形是指这样的一种队形：设K位同学从左到右依次编号为1，2…，K，他们的身高分别为T1，T2，…，TK，&nbsp;&nbsp;&nbsp;则他们的身高满足存在i（1&lt;=i&lt;=K）使得Ti&lt;T2&lt;......&lt;Ti-1&lt;Ti&gt;Ti+1&gt;......&gt;TK。&nbsp; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;你的任务是，已知所有N位同学的身高，计算最少需要几位同学出列，可以使得剩下的同学排成合唱队形。&nbsp; &nbsp; &nbsp;</td> 
 </tr> 
 <tr> 
 <td>知识点:</td> 
 <td>&nbsp;循环&nbsp;</td> 
 </tr> 
 <tr> 
 <td>题目来源:</td> 
 <td>&nbsp;内部整理&nbsp;</td> 
 </tr> 
 <tr> 
 <td>练习阶段:</td> 
 <td>&nbsp;初级&nbsp;</td> 
 </tr> 
 <tr> 
 <td>运行时间限制:</td> 
 <td>无限制</td> 
 </tr> 
 <tr> 
 <td>内存限制:</td> 
 <td>无限制</td> 
 </tr> 
 <tr> 
 <td>输入:</td> 
 <td>&nbsp; 整数N 一行整数，空格隔开，N位同学身高 &nbsp;</td> 
 </tr> 
 <tr> 
 <td>输出:</td> 
 <td>&nbsp; 最少需要几位同学出列 &nbsp;</td> 
 </tr> 
 <tr> 
 <td>样例输入:</td> 
 <td> <pre>8
186 186 150 200 160 130 197 200

</pre> </td> 
 </tr> 
 <tr> 
 <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; 
 }

[http_blog.csdn.net_lisonglisonglisong_article_details_45241965]: http://blog.csdn.net/lisonglisonglisong/article/details/45241965
[DP]: http://blog.csdn.net/lisonglisonglisong/article/details/41548557
[20150424101652021]: /images/20220805/2494d65aa584420f9efbfb3ce604fb0a.png