元組的風(fēng)暴之最長上升子序列
????????小美：還記得我們上次做的那道題目嗎拦焚？求最長連續(xù)遞增子序列的長度父款。
????????阿福：記得啊愈案，當(dāng)時我們用了兩種方法拔疚，分別是在a[i] <=a[i-1]和a[i] > a[i-1]時更新max_len，古老師還表揚(yáng)我們了呢恤左。
????????小美：沒錯贴唇，當(dāng)時你是出盡了風(fēng)頭啊。但是后來我又學(xué)會了一種新的方法飞袋，叫做動態(tài)規(guī)劃戳气，效率更高，代碼也更簡明巧鸭。
????????阿福：真的嗎瓶您？還有這么好的方法？快說給我聽聽。
????????小美：動態(tài)規(guī)劃的概念很復(fù)雜呀袱，我一時半會兒也說不清楚贸毕，但我知道它是一種以空間換時間的方法，它把每個子問題的解都記錄下來了夜赵，這樣就能快速地求出更大規(guī)模問題的解明棍，直到求出最優(yōu)解。具體到這個題目寇僧，就是設(shè)置一個列表d摊腋，用d[i]記錄元素a[i]在子序列中的位置，則最大的d[i]值就是最長子序列長度嘁傀。
題目1：
求最長連續(xù)遞增子序列的長度兴蒸。例如，在元組(1,9,2,5,7,3,4,6,8,0)中最長連續(xù)遞增子序列為(3,4,6,8)心包，其長度為4类咧。
函數(shù)功能：求最長連續(xù)遞增子序列的長度
函數(shù)名：def sub_num(a: tuple) -> int
參數(shù)表：a -- 元組。
返回值：返回最長連續(xù)遞增子序列的長度蟹腾。
示例：輸入a=(1,9,2,5,7,3,4,6,8,0)痕惋，返回4
代碼1：
def sub_num(a: tuple) -> int:
??? if not a: #a是空元組
??????? return 0
??? d = [1] *len(a) # d[i]表示元素a[i]在子序列中的位置
??? for i in range(1, len(a)):
??????? if a[i]> a[i-1]:
??????????? d[i] = d[i-1]+ 1
return max(d)
?????????阿福：確實(shí)不錯啊娃殖！雖然需要多設(shè)置一個列表d值戳，但確實(shí)提高了效率，代碼也更簡潔了炉爆。
????????小美：那還用說堕虹。
????????古老師：士別三日，當(dāng)刮目相待芬首。小美的進(jìn)步很大案袄獭！動態(tài)規(guī)劃是解決最優(yōu)解問題的經(jīng)典算法郁稍，相比暴力枚舉和回溯算法赦政，它的效率要高得多，應(yīng)用也非常廣泛耀怜。我們不妨來看一道類似的問題恢着。
題目2：
求最長上升子序列的長度。例如财破，在元組(1,9,2,5,7,3,4,6,8,0)中最長上升子序列為(1,2,3,4,6,8)掰派，其長度為6。
函數(shù)功能：求最長上升子序列的長度度
函數(shù)名：def lengthOfLIS (a: tuple) -> int
參數(shù)表：a -- 元組左痢。
返回值：返回最長上升子序列的長度靡羡。
示例：輸入a=(1,9,2,5,7,3,4,6,8,0)系洛，返回6
? ? ? ?小美：“最長連續(xù)遞增子序列”和“最長上升子序列”有什么區(qū)別啊亿眠？
?????? 阿福：我的理解是前者必須連續(xù)碎罚，后者可以不連續(xù)磅废。
?????? 古老師：沒錯纳像，它們的區(qū)別就在于是否具有連續(xù)性，“連續(xù)子序列”又稱為“子串”拯勉，要求是一個連續(xù)的序列竟趾；而“子序列”則不一定連續(xù)。
????????小美：哦宫峦，那判斷a[i]是否屬于某個上升序列的時候岔帽，就不僅僅是跟a[i-1]比較，而要與它前面的每一個元素都比較一次导绷，加入到最長的上升序列中犀勒。我可以使用動態(tài)規(guī)劃算法，只需要在代碼1的基礎(chǔ)上修改就行了妥曲。
代碼2：
def lengthOfLIS(self, a: tuple) -> int:
??? if not a:
??????? return 0
??? d = [1] *len(a) #d[i]表示以a[i]為尾元素的上升子序列長度
??? for i in range(1, len(a)):
??????? for j in range(i-1, -1, -1):#逆序掃描a[i]之前的元素贾费，更新d[i]值
??????????? if a[i]> a[j] and d[j] >= d[i]:
???????????????d[i] = d[j] + 1
??? return max(d)
????????阿福：小美是順序掃描元組的，用d[i]記錄元素a[i]在上升子序列中的位置檐盟，或者說d[i]表示以a[i]為尾元素的上升子序列長度褂萧。
????????我也可以逆序掃描元組，求最長下降子序列長度葵萎，用d[i]記錄元素a[i]在下降子序列中的位置导犹，或者說用d[i]表示以a[i]為首元素的上升子序列長度，這樣只要在a[i]后面的元素中找到大于a[i]羡忘，且對應(yīng)d[j]最大的元素a[j]就行了谎痢，我們同樣更新d[i] = d[j] + 1。
代碼3：
def lengthOfLIS(self, a: tuple) -> int:
??? if not a:
??????? return 0
??? d = [1] *len(a) #d[i]表示以a[i]為首元素的上升子序列長度
??? for i in range(len(a)-2, -1, -1):
??????? for j in range(i+1, len(a)):#順序掃描a[i]之后的元素卷雕，更新d[i]值
??????????? if a[i]< a[j] and d[j] >= d[i]:
???????????????d[i] = d[j] + 1
return max(d)
????????古老師：都很不錯节猿！兩種算法中，雖然d[i]的含義不同爽蝴，但都能正確地實(shí)現(xiàn)程序功能沐批，體現(xiàn)了動態(tài)規(guī)劃算法的基本特征。但你們提供的兩種算法時間復(fù)雜度都是O(n^2)蝎亚，能不能將算法的時間復(fù)雜度降低到?O(n?log?n)呢?
????????我只給你們一個提示：使用對分查找算法九孩。
????????好了，我該走了发框，再見躺彬。
彩蛋：
?????? 小美：要將算法的時間復(fù)雜度降低到?O(n?log?n)，那就不能寫成二重循環(huán)的形式了。
?????? 阿福：是的宪拥，原來的內(nèi)層循環(huán)實(shí)際上是一個順序查找最優(yōu)解的過程仿野，現(xiàn)在要把順序查找改成對分查找，這樣就能實(shí)現(xiàn)O(n?log?n)的時間復(fù)雜度了她君。
?????? 小美：對分查找適用于有序列表脚作，可現(xiàn)在列表d并不是有序列表啊。
?????? 阿福：沒錯缔刹。所以不能再使用列表d了球涛，需要設(shè)置一個新的列表s，存儲某些有序的元素校镐∫诒猓可哪些元素是有序的呢？
?????? 小美：我知道了鸟廓，上升子序列就是有序的从祝。列表s就用來存儲最長的上升子序列。
?????? 阿福：漂亮引谜！這就好辦了牍陌。我們可以先把a(bǔ)[0]存儲到s[0]中，之后如果a[i]> s[-1]煌张，就把a(bǔ)[i]添加到列表s尾部呐赡，否則用a[i]替換s中第一個不小于a[i]的元素，使得s中的每個元素都是最小的骏融，這樣可以確保獲得最長序列链嘀。
?????? 小美：什么意思啊档玻？
?????? 阿福：沒聽懂是吧怀泊？我舉個例子給你看看。對于元組a=(1,5,2,6,3,8,2,7,9)误趴，我們用列表s存儲最長上升子序列霹琼。我們初始化s = [a[0]]，之后遍歷a[1:]凉当，若a[i]> s[-1]枣申，則執(zhí)行s.append(a[i])，否則用a[i]替換s中第一個不小于a[i]的元素看杭。這樣可以確保s的尾元素總是最小的忠藤，讓盡可能多的元素加入列表s，從而獲得最長的子序列楼雹。具體操作如下圖模孩。
? ? ? ?小美：這樣我就能看懂了尖阔。那我們在列表s中查找第一個不小于a[i]的元素，是不是需要定義一個函數(shù)來實(shí)現(xiàn)對分查找功能呢榨咐？對分查找算法我學(xué)過介却，有好幾種寫法呢。
?????? 阿福：不用自定義函數(shù)块茁，我記得Python提供了一個標(biāo)準(zhǔn)模塊bisect齿坷，可以用實(shí)現(xiàn)對分查找算法。其中bisect_left(d, x)函數(shù)可以返回列表d中第一個不小于x的元素下標(biāo)龟劲。
?????? 小美：還有這么好用的標(biāo)準(zhǔn)庫啊胃夏，那就省事多了轴或。代碼還是我來寫吧昌跌，你幫我把把關(guān)就行了。
代碼4：
def lengthOfLIS(self, a: tuple) -> int:
??? import bisect
??? if not a:
??????? return 0
??? s = [a[0]]#s[m]表示上升子序列中第m個元素的值
??? for e in a[1:]:
??????? if e >s[-1]:#可將e加入的上升子序列尾部
???????????s.append(e)
??????? else: #用e替換掉s中第一個不小于e的元素照雁，使得s中的每個元素都是最小蚕愤，這樣可以確保獲得最長序列
???????????s[bisect.bisect_left(s, e)] = e
return len(s)
?????? 阿福：真棒！這段代碼通過“力扣”網(wǎng)站測試饺蚊，在所有 python3 提交中擊敗了98.42%的用戶呢萍诱。
