动态规划求最长单调递增子序列

在算法和数据结构中，找到最长单调递增子序列（Longest Increasing Subsequence，LIS）是一个经典的问题。给定一个序列，我们需要找到一个单调递增的子序列，它的长度是所有单调递增子序列中最大的。在本文中，我们将介绍一个动态规划算法来解决这个问题。

1.问题描述

给定一个长度为n的序列a1, a2, a3, ..., an，找到一个最长的单调递增子序列。

举个例子，给定序列 {3，1，4，1，5，9，2，6，5，4}，最长单调递增子序列是{1，4，5，6}，长度为4。请注意，该序列不唯一，{1，2，5，6}，{1，4，5，5}也可以是解决方案。

2.算法思路

（1）定义状态

设dp[i]为以ai这个元素为结尾的最长单调递增子序列的长度。

（2）状态转移方程

对于dp[i]，从dp[1]一直到dp[i-1]这些状态中找到一个长度最长的单调递增子序列，并且最后一个元素小于ai，用这个子序列的长度加1，就是dp[i]的候选答案。 遍历dp[1] ~ dp[i-1]中求得的所有候选答案，取其中大于dp[i-1]的最大值，就是dp[i]的值。

如此一来，dp[i]代表了以ai为结尾的最长单调递增子序列的长度。因为dp[i]夹杂了之前所有状态的信息，所以dp[i]也可以看做是全局最长单调递增子序列的长度。

3.算法实现

//输入数组a

//输出最长单调递增子序列的长度

int LIS(int a[], int n)

{

int dp[n+1];

int len = 1; //找到的最长单调递增子序列的长度

dp[1] = a[1];

for (int i = 2; i <= n; ++i)

{

int j = 1;

while (j <= len && dp[j] < a[i]) ++j;

dp[j] = a[i];

if (j > len) len = j;

}

return len;

}

上面这段代码中，dp[i]的值用一个while循环来求得。这个循环的目的是在dp[1] ~ dp[i-1]中求得所有能作为ai后继状态的答案。要求有序，所以需要用二分查找来优化查找的时间复杂度。

4. 时间复杂度

时间复杂度：O(nlogn)

在真正的实践中，由于动态规划的常数比较小，该算法的实际效率较高，可以解决大多数情况下的问题。

5. 总结

本文介绍了一种动态规划算法解决“最长单调递增子序列”的问题。首先通过定义状态dp[i]来表示以ai为结尾的最长单调递增子序列的长度。然后通过转移方程来求得那些转移状态，最后得出最终结果。时间复杂度为O(nlogn)，效果不错。