编程之美2.16——求数组中最长递增子序列
问题：
求一个一维数组中最长递增子序列的长度。
解法1：
很明显用动态规划的算法，选取下面的阶段（这种选法极为常见），可使阶段间的关系具有无后效性。
阶段：在所有以元素k结尾的子数组中，选出其中的最长递增子序列，k=1,2...n。
状态：以元素k结尾的最长递增子序列中只有一个最长的递增子序列。
决策：决定元素k结尾的最长递增子序列有k-1种获取的途径，前面以任何一个元素结尾的最长递增子序列都可能成为其的一部分。
这样的时间复杂度为O(n^2)，空间复杂度为O(n)
[cpp]
#include <iostream>
#include <algorithm>
using namespace std;
#define MAXN 1003
int A[MAXN];
int dp[MAXN];
// 动态规划思想O(n^2)
int main()
{
int n, i, j, k;
cin >> n;
for (i=1; i<=n; i++)
cin >> A[i];
dp[1] = 1;
// 有n个阶段
for (i=2; i<=n; i++)
{
dp[i] = 1; // 每个阶段只有1个状态
// 每个状态有i种决策,以得出以元素i结尾的最长递归子序列的长度
for (j=i-1; j>=0; j--)
{
if (A[i]>A[j])
dp[i] = max(dp[i], dp[j]+1);
}
}
int maximum = dp[1];
for (i=2; i<=n; i++)
maximum = max(maximum, dp[i]);
cout << maximum;
}
解法2：
动态规划的时间复杂度一般与空间复杂度相同，因为决定下一个阶段的所有条件我们已存储到dp中，在处理过程中我们可以对已得到的这些条件进行处理来降低时间复杂度。而这里时间复杂度竟比空间复杂度高了O(n)，说明还有可以继续优化的空间。
我们可以统计前面所有阶段的最长递增子序列的长度，将长度相同的最长递增子序列分到同一组中，并只记录它们最大元素的最小值MaxV[长度值]，如果阶段k的元素大于长度为i最长递增子序列的这个最小值MaxV[i]，那么阶段k的最长递增子序列的长度至少为i+1。
而我们发现统计出的MaxV数组具有很好的递增关系（动态规划都是用来解决最优化问题，我们总能通过优化关系对之前统计出的结果进行排序），即如果i<j，那么有MaxV[i]<MaxV[j]，最后用二分查找法来阶段k的元素在MaxV数组中的位置即可。
证明：反证法，假设当i<j<=k，有MaxV[i]>=MaxV[j]，那么存在一个长度为i的递增序列a1a2...ai，且ai是计算到阶段k时所有长度为i的递增序列中最大元素的最小值，以及长度为j的序列b1b2...bj且ai>=bj，由于i<j长度j的序列b1b2...bj包含一个子序列b1b2...bi，且bi<bj<=ai，即长度为i的递增子序列最大元素的最小值不是ai，矛盾。
[cpp]
#include <iostream>
#include <algorithm>
using namespace std;
#define MAXN 1003
int A[MAXN];
int MaxV[MAXN];
// 动态规划算法O(nlogn)
int main()
{
int n, i, j, k;
cin >> n;
for (i=1; i<=n; i++)
cin >> A[i];
MaxV[1] = A[1];
int nmaxv = 1; // 目前找到的最长递增子序列的长度
// 有n个阶段，每个阶段有1个状态
for (i=2; i<=n; i++)
{
// 每个状态有nmaxv种决策，以得出以元素i结尾的最长递归子序列的长度
int u = 1, v = nmaxv;
while (u<=v)
{
int mid = (u+v)>>1;
if (MaxV[mid] < A[i])
u = mid+1;
else
v = mid-1;
}
// 每个元素都会对数组MaxV中的某个元素产生影响
// 使用二分搜索确定其在第v+1个位置
nmaxv = max(nmaxv, v+1);
MaxV[v+1] = A[i];
}
cout << nmaxv;
}
作者：linyunzju
补充：软件开发 , C++ ,
