錯題
leetcode 354. 俄羅斯套娃信封問題
錯因和思路：1.心態：因為是自己原來做過的題目就掉以輕心了，導致情況沒有考慮周全
2.思路：將寬度進行排序，高度沒管，如果相同就不改變二分后找到的修改位置，顯然這會少答案要的長度
思路引導：這里根據題目描述很容易想到遞增子序列并將其排序，但是當將寬度進行排序后，會發現高度的選取很麻煩，如果是找遞增子序列還是要管寬度問題，比如說 [[30,50],[12,2],[3,4],[12,15]]
既然如此，那就得換種思路，寬度排序是必須的，怎么才可以在討論高度的時候不討論寬度問題呢？從高處下手，既然不要選同樣的，我們又是要找遞增自序列，大膽想象一下，我們可以在寬度相同的情況下，將高度呈不上升子序列，如此便
可
洛谷P8776 [藍橋杯 2022 省 A] 最長不下降子序列
錯因和思路：這里太興奮了哈哈沒想太多直接找出最長不下降子序列，然后找了個最長的遞增子數組，和k取一個min
思路引導： 首先應該會想到找直接找出最長不下降子序列，然后在里面每個子序列間考慮，不僅要記錄是不是最長子序列里面的，還要考慮會不會跨，而且一般來講我們都不記錄最長子序列到底有哪些數，只記錄答案，所以很麻煩，因此暫時PASS
當問題看似棘手時，就要跳出當前思路，退一步海闊天空
從上面PASS的方案可以看出，其實整個數組的任意連續的k個數都有可能刷成某個數后使得整個數組的最長不下降子序列變長，因此，我們可以枚舉k的位置，像固定的滑窗一樣[l,r)（根據個x人習慣），這樣的話我們只需考慮邊界0——l-1
的最長不降子序列（最后一個值不大于nums[r]),以及r——n-1的最長不降子序列即可
其實，從上面的方案，還可以從另一個角度發現這個思路.就是既然我們可能要跨界限，就不好在算上最長不降子序列的長度后又去處理刷出來的有效的長度，既然如此，秉持著考慮可能性的原則，我們就直接在我們要的答案中的兩個界限
找k個數，什么意思？這里分兩種情況假設（注：這里是找到的最終答案，所以不存在跨界情況）
我們要……A…… B…… C…… [k個被刷的數]…… D…… E……
……A…… B…… C…… [k個被刷的數] D…… E……
obviously，上面的情況和下面的情況的答案實際上是等效的，所以我們直接枚舉k個數在哪，然后找左邊界的最長不降子序列和右邊界開始的最長不降子序列即可
大體流程明白，現在就是怎么找不降子序列的問題。
1）從0_i的 這里最原始的方法就是dp[i]=dp[j]+1 其中是從0-i-1中找到nums[j]<=nums[i]，復雜度比較高，那我們換種思路，就是加一個輔助數組end，表示長度為x的最長不下降子序列的最小的結尾的數是啥，每碰到一個數，就用二
分在里面找一個>這個數 的數的位置，如果沒有就說明沒有在目前最長的不下降子序列中這個數是最大的數，那么在end的有效長度的后面記錄這個數值，并將有效長度擴大。如果找到了，覆蓋即可，并在dp[i]=x
2）從i_n-1的 這個用倒序的最長不下降子序列即可