编程之美这本书里面就有关于这道题的一些解法，求一个一位数组中的最长序列的长度。例如，在序列1，3，2中，最长递增序列是1,3.
这道题，也是腾讯2012校园招聘中的一道题，其实，这道题符合无后效性的要求，我们可以任取从从数组开始时开始的任意子序列，这个子序列的状态无法直接影响将来的决策。换句话说，每个状态是过去历史的一个完整总结。
我们可以定义一个存放每个子序列的最长序列值的数组L，L里面元素的初始值为1，那么不断增长子序列，当遍历到元素i时，如果i代表的元素比前面出现的子序列中的某一元素大的话，那么对应的L数组里面的值就要增一。对应的代码如下.
for(int i=0;i
:L[i] = 1; //初始化长度为1
for(int j=0;j
if(array[i] > array[j]&&L[i]
L[i] = L[j] + 1;
}
}
return max(L);
}
这种方法对应的时间复杂度是O（N2+N）= O（N2）；
其实，我们做到这里的时候，算是初步完成了，但是，我们有时会想，是不是可以进行一点优化，让速度更快？
编程之美里面提供了一中较好的方法，是这样的，它提前记录了前i个元素中，每个子序列中的最小值，MIN（1），MIN（2）.。。。。。然后，对于第i+1个元素，那么只要遍历这些元素，然后对应的最长值增一就行了。好，我们先看一下代码。
MIN[0] = min(array) - 1;//边界，用于子序列为1时可以比较
MIN[1] = array[0];//初始值。
for(0...n-1)
L[i] = 1;//初始化最长子序列
MAXLEN = 1;//最长的子序列数
for(int i=1;i
for(int j=MAXLEN;j>=0;j--){
if(array[i] > MIN[j]){
L[i] = j+1;
break;
}
}
if(L[i] > MAXLEN){
MAXLEN = L[i];
MIN[MAXLEN] = array[i]
}else if(array[j]
MIN[j+1] = array[i];
}
return MAXLEN;
}
咋看一下，其实时间复杂度还是0(n2),但是对于这个我们增加的一个序列对应的最小值，其实具有
单调递增的关系，所以对于这一部分
for(int j=MAXLEN;j>=0;j--){
if(array[i] > MIN[j]){
L[i] = j+1;
break;
}
我们其实可以用二分搜索进行查找，那么时间复杂度就变成了0(n*logN);
阅读(13119) | 评论(0) | 转发(0) |
