NC91 最长递增子序列——题解

#NC91 最长递增子序列
# retrun the longest increasing subsequence
# @param arr int整型一维数组 the array
# @return int整型一维数组
#
class Solution:
    def LIS(self , arr ):
        # write code here
        """
        # 1. 动态规划，超时
        if len(arr) < 2:
            return arr
        
        dp = [1] * len(arr)
        for i in range(1, len(arr)):
            for j in range(i):
                if arr[i] > arr[j]:
                    dp[i] = dp[j] + 1
        
        ansLen = max(dp)
        ansVec = []
        for i in range(len(arr)-1, -1, -1):
            if dp[i] == ansLen:
                ansVec.insert(0, arr[i])
                ansLen -= 1
                
        return ansVec
        """
        
        # 2. 贪心 + 二分
        if len(arr) < 2:
            return arr
        
        ansVec = [arr[0]] # 记录以某一元素结尾的最长递增子序列，初始化为数组第一位元素
        maxLen = [1] # 记录下标i处最长递增子序列的长度，初始化为[1](下标0此时只有一个数字，长度为1)
        
        for num in arr[1:]:
            if num > ansVec[-1]:
                ansVec.append(num)  # 更新以num为结尾元素的最长递增子序列
                maxLen.append(len(ansVec))  # 同时更新此时最长递增子序列的长度
            else:
                """
                for i in range(len(ansVec)):
                    if ansVec[i] >= num:
                        ansVec[i] = num
                        maxLen.append(i+1)
                        break
                """
                # 二分查找第一个比num大的数字，替换
                # 此时以该元素为结尾的最长递增子序列的长度为其在ansVec中的下标+1
                left, right = 0, len(ansVec)-1
                while left < right:
                    mid = (left + right) // 2
                    if ansVec[mid] < num:
                        left = mid+1
                    elif ansVec[mid] == num:
                        left = mid
                        break
                    else:
                        if ansVec[mid-1] < num:
                            left = mid
                            break
                        else:
                            right = mid-1
                ansVec[left] = num
                maxLen.append(left+1)
        
        # ansVec不一定是最后结果，求解按字典序最小的结果
        # 此时我们知道最长长度为ansLen，从后向前遍历maxLen，
        # 遇到第一个maxLen[i]==ansLen的下标i处元素arr[i]即为所求，
        # 例：
        # [1,2,8,6,4] -> maxLen [1,2,3,3,3] -> ansLen=3
        # [1,2,8] -> [1,2,6] -> [1,2,4] 长度一致的答案，字典序越小越靠后
        ansLen = len(ansVec)
        for i in range(len(arr)-1, -1, -1):
            if maxLen[i] == ansLen:
                ansVec[ansLen-1] = arr[i]
                ansLen -= 1
                
        return ansVec
                
#学习路径#