76. Longest Increasing Subsequence
goodwish Sep 21st, 2019 (edited) 117 in 8 hours
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
- way 2: 维护一个排序数组, O(n log n).
- 每次来了新数,找到插入位置 i = bisect_left(),以小换大, 维持升序,
- 如果越界, i == n, 就 append.
- 最后该数组的长度就是 最长子序列长度.
- from bisect import bisect_left
- class Solution:
- def longestIncreasingSubsequence(self, nums):
- A = 
- for v in nums:
- i = bisect_left(A, v)
- if i >= len(A):
- A[i] = v
- return len(A)
RAW Paste Data