给定一个无序整数序列，怎样求其最长递增子序列？#include <deque>#include <cassert>void MaxIncreaseQueue(const std::deque<int> & source,std::deque<int> & result){ typedef std::deque<int> IntArray; //怎样从source中得到最长递增子序列放到result中？}经过分析我们发现，首先，我们要得到这个序列的最小值，所以我们建立了我们的第一个类GetMinValue： class GetMinValue{ int minvalue_;public: explicit GetMinValue(const IntArray & in){ assert(in.size() != 0); IntArray::const_iterator i = in.begin(); for(minvalue_ = *i,++i;i != in.end();++i){ if(minvalue_ > *i) minvalue_ = *i; } } ~GetMinValue(){} operator int() const{ return minvalue_; }};可以看到，GetMinValue以一个IntArray 为参数构造，并由operator int() const来返回其最小值。这样，我们可以这样来得到source的最小值：int min = GetMinValue(source);然后我们开始考虑算法的问题。我想很多人都知道计算机里的堆的概念，一个堆就是一个类似于树的结构，只是它的节点满足一定的排列规则，于是比一般的树更有规律，也更复
杂。我们这里构造这样一个堆（同时也是一棵树，所以我用了Tree这个名字），其父节点的值总比子节点小（或相等），其右节点的值总比左节点小，如图： 2 ——父节点值比子节点小 / / 6 3 ——右节点值比左节点小于是，当我们遍历整个序列的时候，就可以根据以上规则建立这个堆，然后根据深度最大的节点，回溯出整个子序列。第一步我们建立节点的定义：class Node{ int value_,length_; Node *parent_,*rightchild_,*leftbrother_;public: Node(Node * parent,int value):value_(value),length_(1),parent_(parent),rightchild_(0),leftbrother_(0){ if(parent_ != 0){ length_ = parent->length_ + 1; leftbrother_ = parent->rightchild_; parent->rightchild_ = this; } } ~Node(){ if(rightchild_) delete rightchild_; if(leftbrother_) delete leftbrother_; } //Functions for member access int Value() const{ return value_; } int Length() const{ return length_; } Node * Parent() const{ return parent_; } Node * RightChild() const{ return rightchild_; } Node * LeftBrother() const{ return leftbrother_; }};首先看到Node的数据成员，有value_——节点的值，length_——节点的深度（也就是子序列的长度），parent_——父节点的指针（用于回溯），rightchild_——最右的子节点的
指针，leftbrother_——左兄弟的指针。为什么要用rightchild_和leftbrother_而不用几个children_呢？显然大家都能猜到，因为这个树并不一定是二叉树，所以子节点数是不
确定的。然后大家也许会注意到Node的构造函数，必须要提供父节点的指针，这只是一个设计上的问题。我想把所有关于Node指针的操作全放在Node里面，这样就不用把parent_，
rightchild_等定义为public，或提供一个修改的接口。随后是Node的析构函数，2个delete可能会吓坏许多有良好C++编程风格的高手。我只能说，当我把this赋值给parent->rightchild_（Node构造函数里）的时候，就注定了“这样的
结局”(^_^)最后是成员的访问函数，我想应该不会有多少异议。当构造好了节点，我们开始正式构造我们的树（堆）了。树的根root_的value_总是序列里面最小的值（这就是我们定义GetMinValue的原因），这是在树的构造函数里保证的，为
的是让所有可能的序列都能在这个根下生长。而当我们每向树里加入一个值为val的节点时，都要调用AddValue(int val)函数，这个函数进一步调用AddValue(Node * parent,int
val)函数的AddValue(&root,val)版本。AddValue(Node * parent,int val)函数是递规调用的，它的逻辑是这样：如果parent不是一个节点或者val比parent的value_值小，那么返回false，告诉调用者不能插入节点；否则对parent的每一个子节点，如果其value_值比val小，那么应该对其每一
个都调用AddValue；如果没有一个子节点能调用AddValue成功的话，就把val当成parent的子节点插进来。这个规则看似复杂，其实如果有一个流程图来表示，也许会明了得多，可惜我不会在这里画图。现在我想我们应该来看看代码了： class Tree{ Node root_,*max_length_node_; void AddValue(int val){ AddValue(&root_,val); } bool AddValue(Node * parent,int val){ if(!parent || val < parent->Value()) return false; int count = 0; for(Node * p = parent->RightChild();p != 0;p = p->LeftBrother(),++count){ if(!AddValue(p,val)) break; } if(!count) AppendNode(parent,val); return true; } void AppendNode(Node * parent,int val){ Node * p = new Node(parent,val); if(p->Length() > max_length_node_->Length()){ max_length_node_ = p; } }public: explicit Tree(int value):root_(0,value),max_length_node_(&root_){} ~Tree(){} void InputIntArray(const IntArray & in){ for(IntArray::const_iterator i = in.begin();i != in.end();++i){ AddValue(*i); } } void OutputIntArray(IntArray & out){ out.erase(out.begin(),out.end()); Node * p = max_length_node_; while(p != &root_){ out.push_front(p->Value()); p = p->Parent(); } }};大家也许会发现成员变量里的max_length_node_，这是一个追踪深度最大的节点的变量，初始化为&root_，方便最后的回溯。函数AppendNode是真正插入节点的函数，通过一个简单的Node(parent,val)就完成了所有的动作，这就是我前面对Node的构造函数满意的地方。然后是检查深度最大的节点的变化
情况，这一点应该是显而易见的。Tree的构造函数主要用来初始化root_，要使得root_.value_的值是最小的，理由我已经说过了。析构函数更是简单得没有明显的代码。最后是2个接口InputIntArray和OutputIntArray分别用来输入源序列和输出结果序列。注意out.push_front(p->Value())这句，因为我是从最深的子节点向上回溯的，也就是说按
照相反的顺序得到最大子序列，所以用了push_front函数，这也是我使用deque而不用vector的原因。 所有的辅助工具都介绍了，现在你也许要不耐烦的问：“说了这么多，到底怎么得到最大子序列的呢？”那么现在让我们回到最初的MaxIncreaseQueue函数：void MaxIncreaseQueue(const std::deque<int> & source,std::deque<int> & result){ Tree t = Tree(GetMinValue(source)); t.InputIntArray(source); t.OutputIntArray(result);}一切就OK了！如果你对上面的4行代码还有疑问的话，请参阅我前面的一大堆“口水”。 int main(){ typedef deque<int> IntArray; const int size = 30; int array[size] = {5,4,9,4,6,1,7,4,3,5,7,5,3,2,3,4,5,8,1,6,5,4,0,0,1,0,0,0,0,0}; IntArray source(array,array + size),result; MaxIncreaseQueue(source,result); cout<<"Max Queue:"; for(IntArray::const_iterator i = result.begin();i != result.end();++i) cout<<*i<<' '; cout<<'/n'; return 0;}好了，先说到这里，我也累了，下次再聊吧！
