4 lines Python O(n^2)


  • 1

    Build a collection of (lastNumber, length) pairs.

    def lengthOfLIS(self, nums):
        ends = [(float('-inf'), 0)]
        for a in nums:
            ends += (a, max(m + 1 for b, m in ends if a > b)),
        return max(zip(*ends)[1])
    

    Or with nicer variable names...

    def lengthOfLIS(self, nums):
        ends = [(float('-inf'), 0)]
        for num in nums:
            ends += (num, max(length + 1
                              for lastNum, length in ends
                              if num > lastNum)),
        return max(zip(*ends)[1])

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.