本文介绍最长有序（非连续）子序列算法及C++实现。
作者：tyc611.cublog.cn，2008-04-26
[问题描述]
找出由n个元素组成的序列的最长有序子序列长度及其中一个最长有序子序列
（注：这里有序指非递减顺序，且不要求子序列连续）。
例如，对于序列[3, 7, 1, 5, 9, 3]，其中最长有序子序列长度为3，这样的子序列有：
[3, 7, 9]、[1, 5, 9]、[3, 5, 9]。
[算法思想]
利用动态规划的思想，依次处理序列中每个元素，并记录当前已处理序列的结果。
[算法分析与实现]
设数组X的所有元素X[0]、X[1]、…、X[n－1]为目标序列（为了与C/C++语言统一，我们这里下标以0开始）。
算法依次处理序列中每个元素X[i]（i=0..n-1）：
> 当处理完元素X[i]时（下面的M、P是辅助数组）：
1）M[j]表示，在当前已处理序列X[0..i]中，长度为j且以X[k]（k≤i）结束的所有有序子序列中满足X[k]最小的下标k。
2）P[k]表示，在以X[k]（k≤i）结束的最长有序子序列中，X[k]的前一个元素的下标。
3）L表示当前已处理序列X[0..i]中最长有序子序列的长度。
4）子序列X[M[0]]、X[M[1]]、…、X[M[L - 1]]是非递减有序序列，但要注意数组M中的元素值不一定是
有序的（即这些X中的下标可能是乱序的）。
> 当处理完数组X中的所有元素时，L即为原序列的最长有序子序列长度。通过如下方式回溯，我们可以找出一个这样的
最长有序子序列：X[M[L]]、X[P[M[L]]]、X[P[P[M[L]]]]、…。注意，这里的顺序是相反的。
> 处理元素X[i]：
1）在数组M中二分查找元素M[j]，使X[M[j]] ≤ X[i]且j（j ≤ L）最大。如果不存在该元素，则j = 0。
2）P[i] = M[j]。
3）如果j == L，则
L = L+1
M[L] = i
4）否则，如果X[i] < X[M[j+1]]，则
M[j+1] = i
> 初始状态：
M[0] = -1; // 作为哨兵
[算法时间复杂度]
算法时间复杂度为O(nlgn)，空间复杂度也为O(n)
[算法扩展]
前面针对的是非递减有序，还可以针对递增有序、递减有序、非增减有序。
[相关问题] 对于最长连续子序列问题的解答要简单许多，其时间复杂度为O(n)。类似问题还有最大连续或非连续子序列和（
见这里），
这些问题的解决思想都是基于动态规划思想。
[参考资料]
|
/**
* MaxOrderedSubsequence.cpp
* @Author Tu Yongce
* @Created 2008-4-26
* @Modified 2008-4-26
* @Version 0.1
*/
#include <iostream>
#include <vector>
#include <iterator>
#include <algorithm>
using namespace std;
/*
* 计算最长有序子序列（子序列不必连续）
* note: 算法时间复杂度为O(nlgn)，空间复杂度也为O(n)
*/
template <typename T>
struct ArrayIndexCompare
{
const T *arr_;
ArrayIndexCompare(const T *arr): arr_(arr) { }
bool operator() (int lhs, int rhs) const {
return arr_[lhs] < arr_[rhs];
}
};
template <typename T>
void MaxOrderedSubsequence(const T arr[], size_t num, vector<int> &subseqIndices)
{
vector<int> m;
vector<int> pre(num, -1);
m.push_back(-1); // 哨兵
for (int i = 0; static_cast<size_t>(i) < num; ++i) {
// 二分搜索
vector<int>::iterator it = upper_bound(m.begin() + 1, m.end(), i, ArrayIndexCompare<T>(arr));
--it; // 在数组m中二分查找元素m[j]，使arr[m[j]] ≤ arr[i]且j最大
pre[i] = *it; // 记下arr[i]的前驱元素下标
if (it == m.end() - 1)
m.push_back(i); // 比m中对应的元素都大，当前最大子序列增长
else if (arr[i] < arr[*++it])
*it = i; // 长为j + 1的最大子序列的最大值有更小值，需要更新
}
// 将最大有序子序列的数组下标输出
subseqIndices.resize(m.size() - 1);
int indexIn = m[m.size() - 1];
int indexOut = subseqIndices.size() - 1;
while (indexOut >= 0) {
subseqIndices[indexOut--] = indexIn;
indexIn = pre[indexIn];
}
}
void MaxOrderedSubSequenceTest()
{
// 示例1
//int arr[] = {1, 7, 3, 5, 9, 4, 8};
int arr[] = {3, 7, 1, 5, 9, 3};
const size_t NUM = sizeof(arr) / sizeof(arr[0]);
vector<int> subseq;
MaxOrderedSubsequence(arr, NUM, subseq);
cout << "序列：";
copy(arr, arr + NUM, ostream_iterator<int>(cout, " "));
cout << "\n最长有序子序列长度为：" << subseq.size();
cout << "\n最长有序子序列下标为：";
copy(subseq.begin(), subseq.end(), ostream_iterator<int>(cout, " "));
cout << "\n最长有序子序列为：";
for (size_t i = 0; i < subseq.size(); ++i)
cout << arr[subseq[i]] << ' ';
cout << endl;
// 示例2
char arr2[] = {'D', 'A', 'E', 'K', 'T', 'Q', 'H'};
const size_t NUM2 = sizeof(arr2) / sizeof(arr2[0]);
MaxOrderedSubsequence(arr2, NUM2, subseq);
cout << "\n序列：";
copy(arr2, arr2 + NUM2, ostream_iterator<char>(cout, " "));
cout << "\n最长有序子序列长度为：" << subseq.size();
cout << "\n最长有序子序列下标为：";
copy(subseq.begin(), subseq.end(), ostream_iterator<int>(cout, " "));
cout << "\n最长有序子序列为：";
for (size_t i = 0; i < subseq.size(); ++i)
cout << arr2[subseq[i]] << ' ';
cout << endl;
}
|
程序运行输出结果：
|
序列：3 7 1 5 9 3
最长有序子序列长度为：3
最长有序子序列下标为：2 3 4
最长有序子序列为：1 5 9
序列：D A E K T Q H
最长有序子序列长度为：4
最长有序子序列下标为：1 2 3 5
最长有序子序列为：A E K Q |
阅读(3667) | 评论(0) | 转发(0) |
