leetcode

Longest Increasing Subsequence

Longest Increasing Subsequence

Dp Version - 1596ms O(n2)

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
    def lengthOfLIS(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        if not nums: return 0
        dp = [1] * len(nums)
        for i in range(len(nums)):
            for j in range(i):
                if nums[i] > nums[j]:
                    dp[i] = max(dp[i], dp[j] + 1)
        return max(dp)

Binary Search Version - 48ms O(nlogn)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution:
    def lengthOfLIS(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        tails = [0] * len(nums)
        size = 0
        for x in nums:
            i, j = 0, size
            while i != j:
                m = (i + j) // 2
                if tails[m] < x:
                    i = m + 1
                else:
                    j = m
            print(i, j, size, x)
            tails[i] = x
            size = max(i + 1, size)
            print(size, tails)
        return size

test code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
In [250]: n = [1,3,6,7,9,4,10,5,6]
In [253]: s = Solution(); t = s.lengthOfLIS(n); print(t)
6
In [264]: s = Solution(); t = s.lengthOfLIS(n); print(t)
0 0 0 1
1 [1, 0, 0, 0, 0, 0, 0, 0, 0]
1 1 1 3
2 [1, 3, 0, 0, 0, 0, 0, 0, 0]
2 2 2 6
3 [1, 3, 6, 0, 0, 0, 0, 0, 0]
3 3 3 7
4 [1, 3, 6, 7, 0, 0, 0, 0, 0]
4 4 4 9
5 [1, 3, 6, 7, 9, 0, 0, 0, 0]
2 2 5 4
5 [1, 3, 4, 7, 9, 0, 0, 0, 0]
5 5 5 10
6 [1, 3, 4, 7, 9, 10, 0, 0, 0]
3 3 6 5
6 [1, 3, 4, 5, 9, 10, 0, 0, 0]
4 4 6 6
6 [1, 3, 4, 5, 6, 10, 0, 0, 0]
6

leet code

Java/Python Binary search O(nlogn) time with explanation-time-with-explanation)