Solution
from typing import List
class Solution:
def lengthOfLIS(self, nums: List[int]) -> int:
n = len(nums)
f = [1] * n
for i in range(1, n):
for j in range(i):
if nums[j] < nums[i]:
f[i] = max(f[i], f[j] + 1)
return max(f)
if __name__ == "__main__":
sol = Solution()
print(sol.lengthOfLIS([10,9,2,5,3,7,101,18])) # 4
print(sol.lengthOfLIS([0,1,0,3,2,3])) #4
Solution 2
from typing import List
import bisect
class BinaryIndexedTree:
def __init__(self, n: int):
self.n = n
self.c = [0] * (n + 1)
def update(self, x: int, v: int):
while x <= self.n:
self.c[x] = max(self.c[x], v)
x += x & -x
def query(self, x: int) -> int:
mx = 0
while x:
mx = max(mx, self.c[x])
x -= x & -x
return mx
class Solution:
def lengthOfLIS(self, nums: List[int]) -> int:
s = sorted(set(nums))
m = len(s)
tree = BinaryIndexedTree(m)
for x in nums:
rk = bisect_left(s, x) + 1
t = tree.query(rk - 1) + 1
tree.update(rk, t)
return tree.query(m)
if __name__ == "__main__":
sol = Solution()
print(sol.lengthOfLIS([10,9,2,5,3,7,101,18])) #4
print(sol.lengthOfLIS([7,7,7,7])) #1