"""
300
longest increasing subsequence
medium

Given an integer array nums, return the length of the longest
strictly increasing subsequence.

A subsequence is a sequence that can be derived from an array
 by deleting some or no elements without changing the order
  of the remaining elements. For example, [3,6,2,7] is a
  subsequence of the array [0,3,1,6,2,2,7].


"""
from typing import List

class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        memo = [0] *len(nums)
        memo[0] = 1
        for i in range(1, len(nums)):
            temp = 1
            for j in range(0, i):
                if nums[i] > nums[j]:
                    temp = max(temp, memo[j]+1)
            memo[i] = temp
        return max(memo)

sol = Solution()
nums = [7,7,7,7,7]
print(sol.lengthOfLIS(nums))

"""
300
longest increasing subsequence
medium

Given an integer array nums, return the length of the longest
strictly increasing subsequence.

A subsequence is a sequence that can be derived from an array
 by deleting some or no elements without changing the order
  of the remaining elements. For example, [3,6,2,7] is a
  subsequence of the array [0,3,1,6,2,2,7].


"""
from typing import List

class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        memo = [0] *len(nums)
        memo[0] = 1
        for i in range(1, len(nums)):
            temp = 1
            for j in range(0, i):
                if nums[i] > nums[j]:
                    temp = max(temp, memo[j]+1)
            memo[i] = temp
        return max(memo)

sol = Solution()
nums = [7,7,7,7,7]
print(sol.lengthOfLIS(nums))

300 longest increasing subsequence medium  Given an integer array nums, return the length of the longest strictly increasing subsequence.  A subsequence is a sequence that can be derived from an array  by deleting some or no elements without changing the order   of the remaining elements. For example, [3,6,2,7] is a   subsequence of the array [0,3,1,6,2,2,7].