class Solution(object):
def lengthOfLIS(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
#list to keep track of the longest increasing list, the elements are only as placeholders, they are not necessarily the actual longest increasing list
#dynamic programming: everytime we scan a number, the status of which is recorded in the LIS
LIS=[]
def insert(target):
#use binary search to find the index of the element in LIS that is no less than the target
left,right=0,len(LIS)-1
while left<=right:
mid=left+(right-left)/2
if LIS[mid]>=target:
right=mid-1
else:
left=mid+1
#if all the elements in the LIS is smaller than the target, then append the target to LIS
if left==len(LIS):
LIS.append(target)
else:#otherwise, replace the element in the LIS with target, this does not affect the length of the actual LIS already found, but it would not be the actual LIS.
#all the elements after the replaced elements become placeholders that keep track of length of the previously found LIS. when we've replaced all the elements on and after the target elements, we've located a new LIS.
LIS[left]=target
for num in nums:
insert(num)
return len(LIS)
300. Longest Increasing Subsequence
最后編輯于 ：
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
- 文/潘曉璐 我一進(jìn)店門姻几，熙熙樓的掌柜王于貴愁眉苦臉地迎上來宜狐，“玉大人，你說我怎么就攤上這事蛇捌「Ш悖” “怎么了？”我有些...
- 文/不壞的土叔 我叫張陵络拌，是天一觀的道長俭驮。 經(jīng)常有香客問我，道長春贸，這世上最難降的妖魔是什么混萝？ 我笑而不...
- 正文 為了忘掉前任遗遵，我火速辦了婚禮，結(jié)果婚禮上譬圣，老公的妹妹穿的比我還像新娘瓮恭。我一直安慰自己，他們只是感情好厘熟，可當(dāng)我...
- 文/花漫 我一把揭開白布屯蹦。 她就那樣靜靜地躺著，像睡著了一般绳姨。 火紅的嫁衣襯著肌膚如雪登澜。 梳的紋絲不亂的頭發(fā)上，一...
- 文/蒼蘭香墨 我猛地睜開眼晃跺，長吁一口氣：“原來是場噩夢啊……” “哼！你這毒婦竟也來了毫玖？” 一聲冷哼從身側(cè)響起掀虎，我...
- 序言：老撾萬榮一對情侶失蹤，失蹤者是張志新（化名）和其女友劉穎付枫，沒想到半個月后烹玉，有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體，經(jīng)...
- 正文 獨(dú)居荒郊野嶺守林人離奇死亡阐滩，尸身上長有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
- 正文 我和宋清朗相戀三年二打，在試婚紗的時候發(fā)現(xiàn)自己被綠了。 大學(xué)時的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片掂榔。...
- 正文 年R本政府宣布饱溢，位于F島的核電站，受9級特大地震影響走芋，放射性物質(zhì)發(fā)生泄漏绩郎。R本人自食惡果不足惜潘鲫，卻給世界環(huán)境...
- 文/蒙蒙 一、第九天 我趴在偏房一處隱蔽的房頂上張望肋杖。 院中可真熱鬧溉仑，春花似錦、人聲如沸状植。這莊子的主人今日做“春日...
- 文/蒼蘭香墨 我抬頭看了看天上的太陽津畸。三九已至振定，卻和暖如春，著一層夾襖步出監(jiān)牢的瞬間肉拓，已是汗流浹背后频。 一陣腳步聲響...
- 正文 我出身青樓，卻偏偏與公主長得像驻售，于是被迫代替她去往敵國和親露久。 傳聞我的和親對象是個殘疾皇子，可洞房花燭夜當(dāng)晚...
推薦閱讀更多精彩內(nèi)容
- Longest Increasing Subsequence給定一個數(shù)組芋浮，找出longest increasing...
- Given an unsorted array of integers, find the length of l...
- 問題描述 Given an unsorted array of integers, find the length...
- 從第一個開始檢查稳吮，注意沪么，并不是指連續(xù)的序列。詳見題目：https://leetcode.com/problems/...
- d[i] i為結(jié)尾的最長遞增子序列，d[0] = 1 ,d[i] 算出 [0,i) 找出d[i] > d[[0,i...
