题解 | #会议室问题#

class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        #dp[i] = max(dp[i-k] + 1) for k in range(0, i)
        #last = k
        n = len(nums)
        dp = [0]*n
        last = [-1]*n#记录上一个位置
        max_n = 0
        max_i = None
        for i in range(n):
            mk = None
            for k in range(i):
                if nums[k] < nums[i]:
                    if mk is None:
                        mk = k
                    else:
                        if dp[k] > dp[mk]:
                            mk = k
                        elif dp[k] == dp[mk]:
                            if nums[k] < nums[mk]:
                                mk = k
            if mk is None:
                dp[i] = 1
                #last[i] = -1
            else:
                dp[i] = dp[mk] + 1
                last[i] = mk
            
            #max_n = max(max_n, dp[i])
            if max_i is None:
                max_n = dp[i]
                max_i = i
                continue

            if max_n < dp[i]:
                max_n = dp[i]
                max_i = i
            elif max_n == dp[i]:
                if nums[i] < nums[max_i]:
                    max_n = dp[i]
                    max_i = i
        #print(max_n, max_i)
        result = []
        result.append(nums[max_i])
        while True:
            max_i = last[max_i]
            if max_i == -1:
                break
            result.append(nums[max_i])
        result.reverse()
        print(max_n, result)#最长的长度，以及字典序最小的子序列
        return max_n