最长上升子序列(三)

#
# retrun the longest increasing subsequence
# @param arr int整型一维数组 the array
# @return int整型一维数组
#
class Solution:
    def LIS(self , arr ):
        # write code here
#       动态规划，超时，加入maxEnd记录
        if len(arr)<2:
            return arr
        def biSearch(l,r,target,arr):
            while(l<r):
                mid = l+(r-l)//2
                if arr[mid]<=target:
                    l = mid+1
                else:
                    r = mid
            if l == len(arr):
                return l-1
            return l
        n = len(arr)
        dp = [1]*n
        idx = 0
        res = 0
        maxEnd=[arr[0]] # 长度为i+1的子序列最小尾元素
        for i in range(1,n):
            if maxEnd[-1]<arr[i]:
                dp[i] = len(maxEnd)+1
                maxEnd.append(arr[i])
            else:
                idx = biSearch(0,len(maxEnd),arr[i],maxEnd)
                maxEnd[idx] = arr[i]
                dp[i] = idx+1
        ans = []
        res = len(maxEnd)
        for i in range(n-1,-1,-1):
            if res==0:
                break
            if dp[i] == res:
                ans.append(arr[i])
                res-=1
        return ans[::-1]
            
        

#
# retrun the longest increasing subsequence
# @param arr int整型一维数组 the array
# @return int整型一维数组
#
class Solution:
    def LIS(self , arr ):
        # write code here
        if len(arr) < 2:
            return arr
        dp = [arr[0]]
        maxlen = [1]
        for i in range(1, len(arr)):
            if arr[i] > dp[-1]:
                dp.append(arr[i])
                maxlen.append(len(dp))
            else:
                pos = self.binary_search(dp, arr[i])
                dp[pos] = arr[i]
                maxlen.append(pos+1)
        i = len(maxlen) - 1
        j = len(dp)
        while i >= 0:
            if maxlen[i] == j:
                j -= 1
                dp[j] = arr[i]
            i -= 1
        return dp
                
                
    def binary_search(self, dp, num):
        low, high = 0, len(dp) - 1
        while low <= high:
            mid = low + ((high - low) >> 1)
            if dp[mid] == num:
                return mid
            elif dp[mid] > num:
                high = mid - 1
            else:
                low = mid + 1
        return low

class Solution:
    # 二分法 同时得到动态规划中以每个元素结尾最长子升序列长度的列表dp
    def LIS(self, arr):
 
        # 不同长度递增序列的末尾元素，取最小值。
        # 如5 2 6 1 7的三种长度子序列为[1] [2,6] [2,6,7],取末尾tails=[1,6,7]
        # tails的长度是最长递增子序列长度
        tails = [arr[0]]
        # 每个位置上，以该元素结尾的最长递增子序列长度，和动态规划中dp相同
        len_list = [1] * len(arr)
        max_len = 1
        # 二分法找每个元素在tails中的位置，替换最接近且小于它的元素，若最大接在后面
        for i in range(1,len(arr)):
            l, r = 0, len(tails)
            # i中值加1不可能大于j，退出时必然i=j
            while l < r:
                m = (l + r) // 2
                if tails[m] < arr[i]:
                    l = m + 1
                else:r = m
            if l == len(tails):
                tails.append(arr[i])
                max_len += 1
            else:
                tails[l] = arr[i]
            len_list[i] = l+1
 
        res = []
        # 相同长度的子序列，后面的值小，否则若值大可以构成更长序列。
        # 所以每个长度len在len+1出现前的最后一个位置，这个位置的值是结果中第len个
        # 例如      5   2    6   1   7
        # len_list  1  [1]  [2]  1  [3]       结果 [2, 6, 7]
        for i in range(len(arr) - 1, -1, -1):
            if max_len == 0:
                break
            if len_list[i] == max_len:
                res.append(arr[i])
                max_len -= 1
        return res[::-1]

class Solution:
    def LIS(self , arr ):
        n = len(arr)
        dp = [[],[10e9]]
        num = 1
        import copy
        for j in range(n):
            for i in range(1,num + 1):
                if dp[i-1]==[]&nbs***bsp;(dp[i-1]!=[] and dp[i-1][-1]<arr[j]):
                        temp = copy.copy(dp[i - 1])
                        temp.append(arr[j])
                        if sum(temp) < sum(dp[i]):
                            dp[i]=temp
                            num1 = max(num, i+1)
            num=num1
            dp.append([10e9]*(num))
        return(dp[num-1])

#
# retrun the longest increasing subsequence
# @param arr int整型一维数组 the array
# @return int整型一维数组
#
import bisect
class Solution:
    def LIS(self , arr ):
        # write code here
        '''
        先求arr每一个数对应在最长递增子序列中的index，或者说，求添加了arr[i]后，递增子序列的长度。
        （即求最长递增子序列的长度）
        然后根据这个index填充最长递增子序列。
        '''
        array,maxlen = [],[]
        for i in range(len(arr)):
            if not array:
                array.append(arr[i])
                maxlen.append(len(array))
            else:
                if arr[i] > array[-1]:
                    array.append(arr[i])
                    maxlen.append(len(array))
                else:
                    idx = bisect.bisect_left(array, arr[i])
                    array[idx] = arr[i]
                    maxlen.append(idx+1)
                    
        j = len(array)-1
        for i in range(len(arr)-1,-1,-1):
            if j < 0:break
            if maxlen[i]==j+1:
                array[j] = arr[i]
                j-=1
        return array