-
Notifications
You must be signed in to change notification settings - Fork 0
/
300.py
37 lines (27 loc) · 1018 Bytes
/
300.py
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
26
27
28
29
30
31
32
33
34
35
36
37
# 300. Longest Increasing Subsequence
# Given an unsorted array of integers, find the length of longest increasing subsequence.
# Example:
# Input: [10,9,2,5,3,7,101,18]
# Output: 4
# Explanation: The longest increasing subsequence is [2,3,7,101], therefore the length is 4.
# 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.
# Follow up: Could you improve it to O(n log n) time complexity?
from typing import List
class Solution:
def lengthOfLIS(self, nums: List[int]) -> int:
if not nums:
return 0
dp = [1 for _ in nums]
dp[0] = 1
for i in range(0, len(nums)):
for j in range(0, i):
if nums[i] > nums[j]:
dp[i] = max(dp[i], dp[j] + 1)
return dp[-1]
if __name__ == '__main__':
from util import Test
t = Test(Solution().lengthOfLIS)
t.equal(4, [10, 9, 2, 5, 3, 7, 101, 18])
# t.equal()