題目
給定一個(gè)無(wú)序的整數(shù)數(shù)組，找到其中最長(zhǎng)上升子序列的長(zhǎng)度潜的。
示例:
輸入: [10,9,2,5,3,7,101,18]
輸出: 4
解釋: 最長(zhǎng)的上升子序列是 [2,3,7,101]勃救，它的長(zhǎng)度是 4。
說(shuō)明:
可能會(huì)有多種最長(zhǎng)上升子序列的組合捐祠，你只需要輸出對(duì)應(yīng)的長(zhǎng)度即可。
你算法的時(shí)間復(fù)雜度應(yīng)該為 O(n2) 桑李。
進(jìn)階: 你能將算法的時(shí)間復(fù)雜度降低到 O(n log n) 嗎?
來(lái)源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/longest-increasing-subsequence
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有踱蛀。商業(yè)轉(zhuǎn)載請(qǐng)聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請(qǐng)注明出處贵白。
解法
動(dòng)態(tài)規(guī)劃
最簡(jiǎn)單的動(dòng)態(tài)規(guī)劃率拒，一個(gè)一個(gè)讀入數(shù)據(jù)，維護(hù)一個(gè)數(shù)組代表該數(shù)字讀入后戒洼，目前最長(zhǎng)的上升子序列有多長(zhǎng)俏橘。轉(zhuǎn)移條件是：
當(dāng)前面的數(shù)字比當(dāng)前數(shù)字小允华，那些數(shù)字對(duì)應(yīng)的長(zhǎng)度里面圈浇，最大的數(shù)字+1。
舉個(gè)例子靴寂，[9,2,5,3,7,101,18]中：
初始狀況
nums = []
length = []
--------------------
第一步：
nums = [9]
length = [1]
--------------------
第二步：
nums = [9,2]
length = [1,1]
假如nums只有這兩個(gè)磷蜀，那么能找出的最長(zhǎng)上升串只有9或者2，也就是長(zhǎng)度為1.
--------------------
第三步：
nums = [9,2,5]
length = [1,1,2]
比5大的只有2百炬，那么5對(duì)應(yīng)的長(zhǎng)度就是在數(shù)字2對(duì)應(yīng)的長(zhǎng)度+1褐隆，這時(shí)候最長(zhǎng)串是`2,5`
--------------------
第四步：
nums = [9,2,5,3]
length = [1,1,2,2]
--------------------
第五步：
nums = [9,2,5,3,7]
length = [1,1,2,2,3]
以此類推
代碼部分：
class Solution:
def lengthOfLIS(self, nums: List[int]) -> int:
length = [1]*len(nums)
max_length = 0
for i in range(len(nums)):
pre_max = 0
for j in range(i):
if nums[j] < nums[i] and pre_max < length[j]:
pre_max = length[j]
length[i] = pre_max +1
if length[i] > max_length:max_length=length[i]
return max_length
貪心+二分
這個(gè)解釋起來(lái)麻煩一點(diǎn)，基本是也是動(dòng)態(tài)規(guī)劃的改進(jìn)版剖踊。不過(guò)這個(gè)時(shí)候維護(hù)的列表不是讀到某個(gè)字符時(shí)最長(zhǎng)串的長(zhǎng)度庶弃，而是目前最長(zhǎng)串是什么樣衫贬。比如[1,2,9,10,5,6,7,8]最長(zhǎng)串為[1,2,5,6,7,8]。在計(jì)算過(guò)程中我們并不知道最長(zhǎng)串是什么樣歇攻，但是我們可以根據(jù)目前的條件完善最長(zhǎng)串固惯。解釋不易，看個(gè)例子就都懂了缴守。
第1步：
目前的數(shù)組：[1]
維護(hù)的最長(zhǎng)串：[1]
-------------------
第2步：
目前的數(shù)組：[1,2]
維護(hù)的最長(zhǎng)串：[1,2]
-------------------
第3步：
目前的數(shù)組：[1,2,9]
維護(hù)的最長(zhǎng)串：[1,2,9]
-------------------
第4步：
目前的數(shù)組：[1,2,9,10]
維護(hù)的最長(zhǎng)串：[1,2,9,10]
-------------------
第5步：
目前的數(shù)組：[1,2,9,10,5]
維護(hù)的最長(zhǎng)串：[1,2,5,10]
這一步劃重點(diǎn)葬毫！讀到5的時(shí)候，我們可以知道實(shí)際上的最長(zhǎng)串還是[1,2,9,10]這四個(gè)數(shù)字屡穗。
但是贴捡，后面的5意味著，如果后面有很多介于5到9之間的數(shù)字村砂，實(shí)際上最后的答案會(huì)變成[1,2,5,6...]烂斋。
如果后面都是一些極大的數(shù)，最后的最長(zhǎng)串還是[1,2,9,10,...]础废。
但是目前在這一步并不確定后面有什么的情況下源祈，我們把5插入到維護(hù)的最長(zhǎng)串中，替換掉一個(gè)比它大但是最接近5的數(shù)色迂。
實(shí)際上這并不是此時(shí)的最長(zhǎng)串香缺，但是答案要求的僅僅是長(zhǎng)度，而替換并不改變最長(zhǎng)串的長(zhǎng)度歇僧。
這樣的插入好處在于：如果后面還有在5-10中間的數(shù)字图张，那么我們可以用那個(gè)數(shù)字把10替換掉，然后逐步替換成正確的答案诈悍。
實(shí)際上這個(gè)5還有另一種解釋祸轮，5排在第三個(gè)位置，如果我們從當(dāng)前已知的數(shù)組中找出長(zhǎng)度為3的子串侥钳，有[1,2,9] [1,2,5] [1,2,10],[2,9,10].而5是這些里面最小的數(shù)字适袜。
-------------------
第6步：
目前的數(shù)組：[1,2,9,10,5,6]
維護(hù)的最長(zhǎng)串：[1,2,5,6]
-------------------
第7步：
目前的數(shù)組：[1,2,9,10,5,6,7]
維護(hù)的最長(zhǎng)串：[1,2,5,6,7]
-------------------
依次到最后。
實(shí)際上維護(hù)的最長(zhǎng)串是個(gè)遞增的數(shù)組舷夺，這樣插入（替換）的時(shí)候就可以用二分法查找苦酱。
代碼：
class Solution(object):
def lengthOfLIS(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
if not nums:
return 0
string = [nums[0]]
for num in nums:
# 二分法查找插入點(diǎn)
i, j = 0,len(string)
while i < j :
m = (i+j)//2
if string[m] < num: i = m+1 # 替換更大的數(shù)字，所以可以+1给猾，不然可能死循環(huán)
else: j = m
if i >= len(string): string.append(num)
else: string[i] = num
return len(string)
總結(jié)
用在長(zhǎng)度為i的子串末尾的數(shù)字來(lái)作為表格很關(guān)鍵疫萤。
