动态规划系列之最长递增子序列问题解答

今天和大家分享的是动态规划经典问题:最长递增子序列问题解答。(似乎BAT等各大公司都喜欢在面试的时候对动态规划系列经典问题进行笔试。

题目描述:

给定一个整数序列:

求其最长递增子序列(LIS)。如果该序列的一个子序列

其满足且

那么该子序列称为该序列的递增子序列。最长递增子序列就是最长的递增子序列,可能不是唯一的。比如序列为5,2,8,6,3,6,9,7,那么其一个最长递增子序列为2,3,6,9。

思路分析

如果采用暴力穷举,那么时间复杂度是O(2^n),这是难以让人接收的。可以采用动态规划的方式,将问题拆分,我们可以考虑以某一个元素ak为结束元素的最长递增子序列,这里记其长度为L[k],如果我们把所有的情况都计算出来,找到最长的那么就是原问题的最长递增子序列。然后我们要考虑这个子问题是否可以用比其更小的问题递归出来。答案是可以的,如果我们已经知道了L[1],L[2],…,L[k-1],我们可以遍历它们,如果某个元素aj恰好是不大于ak,那么这个递增子序列可以后面加上生成新的递增子序列,并且长度为L[j]+1。我们遍历a1,a2……ak-1,找出最大值就是L[k]。递归公式为:

上面是可以计算出序列的最长递增子序列的长度,时间复杂度为O(n^2)。如果你想得到最终的最长递增子序列,那么可以记录上面递归公式中遍历时的最长情况下的前接元素索引,然后通过这些索引可以重构出最长递增子序列,具体可以参见下面的代码。

具体实现代码(C++)

vector<int> lis(const vector<int>& s)

{
 vector<int> ls(s.size(), 0);
 vector<int> ps(s.size(), -1);
 // 对于k=1
 ls[0] = 1;   // 只有一个元素
 ps[0] = -1;  // 无前接元素
 for (int i = 1; i < s.size(); ++i)
    {
 ls[i] = 1;  // 仅含有自己
 for (int j = 0; j < i; ++j)
        {
 if (s[j] <= s[i] && ls[i] < 1 + ls[j])
            {
 ls[i] = 1 + ls[j];
 ps[i] = j;
            }
        }
    }
 int pos = max_element(ls.begin(), ls.end()) - ls.begin(); // lis的最大元素位置
 vector<int> result;
 result.push_back(s[pos]);
 // 通过前接元素索引重构最长递增子序列
 while (ps[pos] != -1)
    {
 pos = ps[pos];
 result.push_back(s[pos]);
    }
 reverse(result.begin(), result.end());
 return result;
}

优化分析

前面的计算时间复杂度是O(n^2),那么有没有更高效的算法。我们先看看之前算法可以改进的地方,你要找到L[k],你必须要把前面的k-1个子问题遍历一遍,这个是O(n)的时间复杂度。由于前面k-1个问题是无序的,你不知道哪个子问题是最优的,所以我们要全部遍历。如果是有序的话,我们可以采用二分查找,那么时间复杂度将为O(logn)。我们考虑这样的子问题,假定a1,a2……ak-1的LIS为

L,并且我们维护了长度分别为1,2……L的递增子序列的末尾元素的最小值,这里递增子序列长度为i的末尾元素最小值记为M[i]。明显M序列是有序递增的。当加入元素ak时,如果M[l]≥ak,那么序列a1,a2……ak的LIS为L+1,且M[l+1]=ak。否则,你需要遍历M[1],M[2],…,M[l],找到第一个满足M[i]≥ak所对应的i,并且更新M[i]=ak,这时我们更新只是维持数组M的特性,这样后面继续加入新元素,可以重复前面的过程,但是其实元素ak的加入并不会为当前整个序列的LIS做贡献。由于M是有序的,那么可以采用二分查找方式,这样最终的时间复杂度为O(nlogn)。最后M的长度就等于最长递增子序列的长度,但是M并不是最长递增子序列,这点要注意。如果序列是4,1,6,2,8,5,7,3,其整个过程如下图所示:

最终实现代码如下:

vector<int> lis(const vector<int>& s)
{
 vector<int> m;
 // 初始化
 m.push_back(s[0]);
 for (int i = 1; i < s.size(); ++i)
    {
 // lis增加1
 if (s[i] >= m.back())
        {
 m.push_back(s[i]);
        }
 else
        {
 // 利用lower_bound函数找到第一个大于或等于s[i]的位置
            *lower_bound(m.begin(), m.end(), s[i]) = s[i];
        }
    }
 return m;
}

原文发布于微信公众号 - 机器学习算法全栈工程师(Jeemy110)

原文发表时间:2017-09-18

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏java一日一条

19 个 JavaScript 编码小技巧

这篇文章适合任何一位基于JavaScript开发的开发者。我写这篇文章主要涉及JavaScript中一些简写的代码,帮助大家更好理解一些JavaScript的基...

624
来自专栏小樱的经验随笔

KMP算法学习(详解)

kmp算法又称“看毛片”算法,是一个效率非常高的字符串匹配算法。不过由于其难以理解,所以在很长的一段时间内一直没有搞懂。虽然网上有很多资料,但是鲜见好的博客能简...

2525
来自专栏北京马哥教育

8大排序算法图文讲解

排序算法可以分为内部排序和外部排序,内部排序是数据记录在内存中进行排序,而外部排序是因排序的数据很大,一次不能容纳全部的排序记录,在排序过程中需要访问外存。 ...

5027
来自专栏玄魂工作室

如何学Python 第七课 列表型变量 列表方法 列表索引

在上一篇文章里,我们介绍了if语句、elif语句和else语句以及条件判断语句。我们今天来说点流程控制之外的东西:列表。列表型变量可以在变量下存储多个值,并以索...

3197
来自专栏武培轩的专栏

剑指Offer-二维数组中的查找

package Array; /** * 二维数组中的查找 * 在一个二维数组中,每一行都按照从左到右递增的顺序排序,每一列都按照从上到下递增的顺序排序。...

2483
来自专栏数据结构与算法

30:字符环

30:字符环 总时间限制: 1000ms 内存限制: 65536kB描述 有两个由字符构成的环。请写一个程序,计算这两个字符环上最长连续公共字符串的长度。例...

4129
来自专栏desperate633

LintCode 合并排序数组 II题目代码

合并两个排序的整数数组A和B变成一个新的数组。 注意事项 你可以假设A具有足够的空间(A数组的大小大于或等于m+n)去添加B中的元素。

412
来自专栏magicsoar

Effective Modern C++翻译(2)-条款1:明白模板类型推导

第一章 类型推导 C++98有一套单一的类型推导的规则:用来推导函数模板,C++11轻微的修改了这些规则并且增加了两个,一个用于auto,一个用于decltyp...

17710
来自专栏JetpropelledSnake

Python入门之三元表达式\列表推导式\生成器表达式\递归匿名函数\内置函数

本章目录:     一、三元表达式、列表推导式、生成器表达式     二、递归调用和二分法     三、匿名函数     四、内置函数 ============...

3335
来自专栏灯塔大数据

码农必看:8大排序算法图文详解

排序算法可以分为内部排序和外部排序,内部排序是数据记录在内存中进行排序,而外部排序是因排序的数据很大,一次不能容纳全部的排序记录,在排序过程中需要访问外存。 ...

3839

扫描关注云+社区