http://acm.pku.edu.cn/JudgeOnline/problem?id=1887

（最長非單調(diào)增序列，，要用N*LOG N（不然會超時。））

二分模板：

int Find(int a,int end)

{

???????? if(a>=ans[1])return 1;

???????? for(int beg=1;beg!=end-1;)

???????? {

?????????????????? int mid=(beg+end)/2;

?????????????????? if(ans[mid]<=a)end=mid;

?????????????????? else beg=mid;

???????? }

???????? return end;

}

剛開始這個N*LOGN的算法主要是二分的方面取優(yōu)

然而，，鴨子的一句話讓我仔細想想

我才發(fā)現(xiàn)

巧妙的是他不是根據(jù)原先N^2的算法在原地取優(yōu)，而是換一種思維，用另外一個數(shù)組來記錄

數(shù)組ans[i]記錄長度為i的最優(yōu)序列的最小值的最大值，

感覺像是貪心多一點，這是一個值得反復琢磨的算法，相信在以后會有很大的用處，，

轉(zhuǎn)載于:https://www.cnblogs.com/gdutbean/archive/2010/03/27/1698248.html

創(chuàng)作挑戰(zhàn)賽新人創(chuàng)作獎勵來咯，堅持創(chuàng)作打卡瓜分現(xiàn)金大獎

總結

以上是生活随笔為你收集整理的最长非单调增序列（最长非单调增序列，，要用N*LOG N（非常值得琢磨的算法。）...的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。