怎么开通公司网站,重庆网站制作企业,旅行WordPress主题,申请注册网站转载自#xff1a;最长上升子序列(LIS)长度的O(nlogn)算法 最长上升子序列nlogn算法 在川大oj上遇到一道题无法用n^2过于是#xff0c;各种纠结#xff0c;最后习得nlogn的算法 最长递增子序列#xff0c;Longest Increasing Subsequence 下面我们简记为 LIS。排序LCS算法 …转载自最长上升子序列(LIS)长度的O(nlogn)算法 最长上升子序列nlogn算法 在川大oj上遇到一道题无法用n^2过于是各种纠结最后习得nlogn的算法 最长递增子序列Longest Increasing Subsequence 下面我们简记为 LIS。排序LCS算法 以及 DP算法就忽略了这两个太容易理解了。 假设存在一个序列d[1..9] 2 1 5 3 6 4 8 9 7可以看出来它的LIS长度为5。n下面一步一步试着找出它。我们定义一个序列B然后令 i 1 to 9 逐个考察这个序列。此外我们用一个变量Len来记录现在最长算到多少了 首先把d[1]有序地放到B里令B[1] 2就是说当只有1一个数字2的时候长度为1的LIS的最小末尾是2。这时Len1 然后把d[2]有序地放到B里令B[1] 1就是说长度为1的LIS的最小末尾是1d[1]2已经没用了很容易理解吧。这时Len1 接着d[3] 5d[3]B[1]所以令B[11]B[2]d[3]5就是说长度为2的LIS的最小末尾是5很容易理解吧。这时候B[1..2] 1, 5Len2 再来d[4] 3它正好加在1,5之间放在1的位置显然不合适因为1小于3长度为1的LIS最小末尾应该是1这样很容易推知长度为2的LIS最小末尾是3于是可以把5淘汰掉这时候B[1..2] 1, 3Len 2 继续d[5] 6它在3后面因为B[2] 3, 而6在3后面于是很容易可以推知B[3] 6, 这时B[1..3] 1, 3, 6还是很容易理解吧 Len 3 了噢。 第6个, d[6] 4你看它在3和6之间于是我们就可以把6替换掉得到B[3] 4。B[1..3] 1, 3, 4 Len继续等于3 第7个, d[7] 8它很大比4大嗯。于是B[4] 8。Len变成4了 第8个, d[8] 9得到B[5] 9嗯。Len继续增大到5了。 最后一个, d[9] 7它在B[3] 4和B[4] 8之间所以我们知道最新的B[4] 7B[1..5] 1, 3, 4, 7, 9Len 5。 于是我们知道了LIS的长度为5。 !!!!! 注意。这个1,3,4,7,9不是LIS它只是存储的对应长度LIS的最小末尾。有了这个末尾我们就可以一个一个地插入数据。虽然最后一个d[9] 7更新进去对于这组数据没有什么意义但是如果后面再出现两个数字 8 和 9那么就可以把8更新到d[5], 9更新到d[6]得出LIS的长度为6。 然后应该发现一件事情了在B中插入数据是有序的而且是进行替换而不需要挪动——也就是说我们可以使用二分查找将每一个数字的插入时间优化到O(logN)~~~~~于是算法的时间复杂度就降低到了O(NlogN) #includecstdio
#includeiostream
#includecstring
#define MAXN 40005
using namespace std;
int arr[MAXN],ans[MAXN],len;
int binary_search(int i){int left,right,mid;left1,rightlen1;while(leftright){mid (rightleft)1;if(ans[mid]arr[i]) rightmid-1;else leftmid1;}return left;
}int main()
{ int T,p,i,j,k;scanf(%d,T);while(T--){scanf(%d,p);for(i1; ip; i)scanf(%d,arr[i]);ans[1] arr[1];len1;for(i2; ip; i){if(arr[i]ans[len])ans[len]arr[i];else{int posbinary_search(i);//可以使用lower_bound(ans1,anslen1,arr[i])-ansans[pos] arr[i];}}printf(%d\n,len);} return 0;
}转载于:https://www.cnblogs.com/Slager-Z/p/7787564.html
