马戏团叠罗汉-之最长递增子序列

2、真正的问题：最长递增子序列，每个元素均为一对项目

          现在，我们知道如何找出一串整数的最长递增子序列，就可以很容易地解决真正的问题，只要将一列表演人员按身高排序，然后对体重套用longestIncreasingSubsequence算法。

下面是该算法的实现代码：

       ArrayList<HtWt> getIncreasingSequence(ArrayList<HtWt> items)
{
Collections.sort(items);
return longestIncreasingSubsequence(items);
}
void longestIncreasingSubsequence(ArrayList<HtWt> array,ArrayList<HtWt>[] solutions,int current_index)
{
if(current_index>=array.size()||curent_index<0) return ;
HtWt current_element=array.get(current_index);
//找出可以附加current_element的最长子序列
ArrayList<HtWt> best_sequence=null;
for(int i=0;i<current_index;i++)
{
if(array.get(i).isBefore(current_element))
{
best_sequence=seqWithMaxLength(best_sequence,solutions[i]);
}
}
//附加current_element
ArrayList<HtWt> new_solution=new ArrayList<HtWt>();
if(best_sequence!=null)
{
new_solution.addAll(best_sequence);
}
new_solution.add(current_element);
//加入懂啊列表中，然后递归
solutions[current_index]=new_solution;
longestIncreasingSubsequence(array,solutions,current_index+1);
}
ArrayList<HtWt> longestIncreasingSubsequenc(ArrayList<HtWt> array)
{
ArrayList<HtWt>[] solutions=new ArrayList[array.size()];
longestIncreasingSubsequence(array,solutions,0);
ArrayList<HtWt> best_sequence=null;
for(int i=0;i<array.size();i++)
{
best_sequence=seqWithMaxLength(best_sequence,solutions[i]);
}
return best_sequence;
}
//返回较长的序列
ArrayList<HtWt> seqWithMaxLength(ArrayList<HtWt> seq1,ArrayList<HtWt> seq2)
{
if(seq1==null) return seq2;
if(seq2==null) return seq1;
return seq1.size()>seq2.size()?seq1:seq2;
}
public class HtWt implements Comparable
{
//声明等,供sort方法使用
public int compareTo(Object s)
{
HtWt second=(HtWt) s;
if(this.Ht !=second.Ht)
{
return ((Integer)this.Ht).compareTo(second.Ht);
}
else
{
return ((Integer)this.Wt).compareTo(second.Wt);
}
}
/*
* 若this应该排在other之前，则返回true
* 注意，this.isBefore(other)和other.isBefore(this)
* 两者皆为false,这跟compareTo方法不同，若a<b,则b>a
*/
public boolean isBefore(HtWt other)
{
if(this.Ht<other.Ht && this.Wt<other.Wt)
return true;
else
return false;
}
}

这个算法的时间复杂度为O(n2).