Python solution based on LIS
It's a problem based on LIS.  \nDP solution for LIS is N^2 which will TLE here.\nUsing Binary Search approach will get accepted.\n\nhttps://leetcode.com/problem
It's a problem based on LIS.  \nDP solution for LIS is N^2 which will TLE here.\nUsing Binary Search approach will get accepted.\n\nhttps://leetcode.com/problems/longest-increasing-subsequence/\n\n    def maxEnvelopes(self, envelopes):\n        """\n        :type envelopes: List[List[int]]\n        :rtype: int\n        """\n        if not envelopes:\n            return 0\n        \n        l = len(envelopes)\n        if l == 1:\n            return 1\n        \n        envelopes.sort(\n            cmp = lambda x, y: x[0] - y[0] if x[0] != y[0] else y[1] - x[1]) \n        # sort the envelopes by width because they need to be inorder before consider the heigths or versa\n        \n        width = []\n        for i in envelopes:\n            width.append(i[1])\n            \n        res = self.longestSubsequence(width)\n        # the problem became LIS after sort(width)\n        \n        return res\n        \n        \n    \n    def longestSubsequence(self, nums):\n        """\n        return type: int (number of longest subsequence)\n        """\n        if not nums:\n            return 0\n        l = len(nums)\n        res = []\n        \n        for num in nums:\n            pos = self.binarySearch(num, res)\n            if pos >= len(res):\n                res.append(num)\n            else:\n                res[pos] = num\n        \n        return len(res)\n        \n        \n    \n    def binarySearch(self, target, nums):\n        """\n        return type: int (ceiling of the insert position)\n        """\n        if not nums:\n            return 0\n        \n        l = len(nums)\n        start = 0\n        end = l - 1\n        \n        while start <= end:\n            half = start + (end - start) // 2\n            if nums[half] == target:\n                return half\n            elif nums[half] < target:\n                start = half + 1\n            else:\n                end = half - 1\n            \n        return start\n'''
['Python']