SHARE
TWEET

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!
  1. way 2: 维护一个排序数组, O(n log n).
  2. 每次来了新数,找到插入位置 i = bisect_left(),以小换大, 维持升序,
  3. 如果越界, i == n, 就 append.
  4. 最后该数组的长度就是 最长子序列长度.
  5.  
  6. from bisect import bisect_left
  7. class Solution:
  8.     def longestIncreasingSubsequence(self, nums):
  9.         A = []
  10.         for v in nums:
  11.             i = bisect_left(A, v)
  12.             if i >= len(A):
  13.                 A.append(v)
  14.             else:
  15.                 A[i] = v
  16.         return len(A)
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top