Longest increasing subsequence#
Practice Link#
Description#
- Given an unsorted array of integers, find the length of longest increasing subsequence.
Note:
- There may be more than one LIS combination, it is only necessary for you to return the length.
- Your algorithm should run in O(n2) complexity.
Example#
1Input: [10,9,2,5,3,7,101,18]
2Output: 4
3Explanation: The longest increasing subsequence is [2,3,7,101], therefore the length is 4.Follow up#
- Could you improve it to O(n log n) time complexity?
Python Solution#
1class Solution(object):
2 def lengthOfLIS(self, nums):
3 tails = [0] * len(nums)
4 size = 0
5 for x in nums:
6 i, j = 0, size
7 while i != j:
8 m = (i + j) / 2
9 if tails[m] < x:
10 i = m + 1
11 else:
12 j = m
13 tails[i] = x
14 size = max(i + 1, size)
15 return size