动态规划系列之最长递增子序列问题解答
今天和大家分享的是动态规划经典问题：最长递增子序列问题解答。（似乎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)。如果你想得到最终的最长递增子序列，那么可以记录上面递归公式中遍历时的最长情况下的前接元素索引，然后通过这些索引可以重构出最长递增子序列，具体可以参见下面的代码。
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;
}
扫描燕哥微信号，
拉你进机器学习大牛群。
福利满满，名额已不多…
群里目前包括：
清华张长水教授，
清华顾险峰教授，
北大黄铁军教授，
西安电子科技大学焦李成教授，
新加坡南洋理工大学黄广斌教授，
北交李清勇教授
等等……