upper_bound只會替換讓留在數組里的最長遞增子序列盡可能小
由于upper查出來的結果下標是那個可以插入這個值得最后一個元素
所以他會把大的數變成小的數

upper將可以替換成新元素的元素替換成更小的
將不能替換的元素 大的元素直接放在最后面
很神奇

你會發現 這個問題
通過一個二分就能解決
如何解決的呢
我們要在vector中維護一個遞增序列
如何維護
那就是每當我們遍歷過程中拿到一個元素
考慮如果這個元素比我們維護的最大遞增數列的最大值還要大
就插在最后
如果比那個序列的最大值小
就需要在序列中
找到一個地方 放下這個值 使得我們整個序列的長度還是沒變
但是能夠替換某個元素使得這個序列中的某些元素變小
從而達到當我新來一個元素時能夠盡可能插入進去
擴增LIS的長度的效果
因為在一個數組X中
X中的遞增序列可能有多個
其中一定是最小的那個序列（對應元素盡可能的小）是LIS
比如在1 2 100 2 2中
LIS 1 2 2 2
那么 如果我們維護的是 1 2 100
此時就得不到最終的LIS 由于不是嚴格遞增
所以我們要選擇upperbound 要在維護的數列中選擇
插入上界 跳過相等的元素 用2替換100使得序列盡可能長
而如果題目要求的是 嚴格遞增
我們拿到一個新元素小于維護數列的最大元素時
就需要lowerbound插進去因為 我們要替換的是相等的元素
不過如果原來的序列中并沒有與插入元素相等的元素
我們用lower_bound仍然會替換得到的序列會更小

**所以LIS問題
非嚴格遞增 用upperbound維護 以為每次遇到一個相等的元素我們可以延長他相等的長度
從而增大LIS的長度 （注意雖然這里可以增大LSI的長度 但我們得到的并非是真正的LIS
我們只是得到了長度 比如對于1 2 3 4 5 2 2 這個序列 如果我們用uper維護
那么到我我們得到的序列是 1 2 3 4 5 繼續處理我們得到了 1 2 2 2 5 雖然在原始中并不存在這個序列
但是他符合我們最長的要求 如果后面有更多的2 也就是可以把前面的大數全部覆蓋
例如 我們得到了1 2 3 4 5 2 2 2 -〉我們得到最長的序列就是 1 2 2 2 2 假如原序列后面有個3
我們正好把他插入進去 得到名副其實的LIS 但如果我們不用upper維護 我們就得不到這個長度
所以雖然輔助數組中存的不是真正的LIS 但我們維護的策略是盡可能得到LIS的長度而非LIS
假如數列中最大值后面的元素數量不足以覆蓋最大值 那么我們就算是LIS 依舊是在真正的LIS上進行操作
不會對真正的LIS長度造成影響
如果數列最大值后面的元素足夠多了覆蓋了最大值而且后面還能繼續增加長度
那么我們這里的覆蓋就是合理的 為了得到LIS的最大長度 這是我們的唯一選擇
）
嚴格遞增 用lowerbound插入比維護數組小的元素（
如上面的例子 我們用upper維護得到的是非嚴格遞增的
那么用lower維護 遇到序列里已經存在的值 我們lower一下并沒有任何實質性改變
所以用lower維護出來的一定是嚴格遞增的最大值
）
時間復雜度O(nlogn)**

所以用二分去構造LIS的原因在于 二分插入的過程就是我們自己手工找出LIS的過程
遇到更大的值就插入LIS 否則就不斷替換我們找到的數串以找到更長的LIS

總結

以上是生活随笔為你收集整理的LIS 的 n*log 算法 ———二分维护的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。