leetcode-300-Longest Increasing Subsequence

amc 發(fā)布于2019-07-30 17:36 / 3237人閱讀

摘要：本質(zhì)找出最長(zhǎng)的遞增子序列的長(zhǎng)度，可以是不連續(xù)的。應(yīng)用判斷滿足一定條件的子序列的最大長(zhǎng)度，用動(dòng)態(tài)數(shù)組加以處理。二分法確定滿足條件的位置。類似二分法查找元素，查找某種情況的子序列。

本質(zhì)： 找出最長(zhǎng)的遞增子序列的長(zhǎng)度，可以是不連續(xù)的。

  用一個(gè)數(shù)組存儲(chǔ) 遞增子序列，遍歷原始數(shù)組，每增加一個(gè)數(shù)，往里添加到對(duì)應(yīng)的順序，記錄他的位置，即為此數(shù)組的長(zhǎng)度。
  成立的理由：每一個(gè)數(shù)添加以后，都有對(duì)應(yīng)的子序列的長(zhǎng)度，將它記錄即可，然后最后取一個(gè)最長(zhǎng)的。

思考：數(shù)組作為記錄的作用，可以記錄滿足條件的數(shù)值，index可以作為索引，

  可以記錄子數(shù)組，從中獲取子數(shù)組的長(zhǎng)度， 可以子數(shù)組修改子數(shù)組，加以覆蓋，修改，根據(jù)最后一個(gè)值判斷l(xiāng)ength。

應(yīng)用： 判斷滿足一定條件的子序列的最大長(zhǎng)度，用動(dòng)態(tài)數(shù)組加以處理。

  二分法確定滿足條件的位置。
  思路： 將滿足條件的數(shù)值記錄在數(shù)組，然后每次新數(shù)值插入此數(shù)組，記錄下此時(shí)需要的信息。

類似： 二分法查找元素，查找某種情況的子序列。

class Solution:
    def lengthOfLIS(self, nums):
        length=len(nums)
        dp=[0]*length
        size=0
        for index,num in enumerate(nums):
            i,j=0,size
            while i!=j:
                m=(i+j)//2
                if dp[m]num:
                    j=m
                else:
                    i=m
                    break
            dp[i]=num
            size=max(size,i+1)
        return size
if __name__ == "__main__":
    nums = [10, 9, 2, 5, 3, 7,8,10,14,18,101,18,16,17,18]
    # nums=[3,1,4,1,5,9,2,6]
    print(len(nums))
    st = Solution()
    out=st.lengthOfLIS(nums)
    print(out)