<p>Given an integer array <code>nums</code>, return <em>the length of the longest <strong>strictly increasing </strong></em><span data-keyword="subsequence-array"><em><strong>subsequence</strong></em></span>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> nums = [10,9,2,5,3,7,101,18]
<strong>Output:</strong> 4
<strong>Explanation:</strong> The longest increasing subsequence is [2,3,7,101], therefore the length is 4.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> nums = [0,1,0,3,2,3]
<strong>Output:</strong> 4
</pre>

<p><strong class="example">Example 3:</strong></p>

<pre>
<strong>Input:</strong> nums = [7,7,7,7,7,7,7]
<strong>Output:</strong> 1
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= nums.length &lt;= 2500</code></li>
	<li><code>-10<sup>4</sup> &lt;= nums[i] &lt;= 10<sup>4</sup></code></li>
</ul>

<p>&nbsp;</p>
<p><b>Follow up:</b>&nbsp;Can you come up with an algorithm that runs in&nbsp;<code>O(n log(n))</code> time complexity?</p>

class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:































        dp = [1] * len(nums)

        for i in range(len(dp)-1, -1, -1):
            for j in range(i, len(dp)):
                if nums[i] < nums[j]:
                    dp[i] = max(dp[i], dp[j]+1)
        # print(dp)
        return max(dp)
























        # dp = [1] * len(nums)

        # for i in range(len(nums)-1,-1,-1):
        #     for j in range(i, len(nums)):
        #         if nums[i] < nums[j]:
        #             dp[i] = max(dp[i], dp[j] + 1)
        
        # return max(dp)



































        # stack = []
        # for n in nums:
        #     ind = bisect.bisect_left(stack, n)
        #     if ind == len(stack):
        #         stack.append(n)
        #     else:
        #         stack[ind] = n

        # return len(stack)









      # if not nums:
        #     return 0
        
        # sub = []
        # for n in nums:
        #     ind = bisect.bisect_left(sub, n)
        #     if ind == len(sub):
        #         sub.append(n)
        #     else:
        #         sub[ind] = n
        # return len(sub)




        # if not nums:
        #     return 0
        
        # sub = []
        # for num in nums:
        #     #이건 sorted order로 합치겠다는 뜻으로써
        #     #num이 지금 있는 이 sub라는 리스트 몇 번째에 삽입되어야 increasing order 인가를 뱉음
        #     ind = bisect.bisect_left(sub, num)
        #     #그래서 만약 지금 삽입하려는 num이 sub의 어떤 숫자들보다 커서 ind가 len(sub)가 되면 append! 
        #     if ind == len(sub):
        #         sub.append(num)
        #     #아니면 더 작은 숫자로 대체 해버림
        #     else:
        #         sub[ind] = num
        # return len(sub)                















        # if not nums:
        #     return 0
        # sub = []
        # for num in nums:
        #     pos = bisect.bisect_left(sub, num)
        #     if pos == len(sub):
        #         sub.append(num)
        #     else:
        #         sub[pos] = num
        # return len(sub)




































        # dp = [1] * len(nums)
        
        # for i in range(len(nums)-2, -1 ,-1):
        #     for j in range(i+1, len(nums)):
        #         if nums[i] < nums[j]:
        #             dp[i] = max(dp[i], dp[j] + 1)
        
        # return max(dp)
            

































        # dp = [1] * len(nums)
        
        # for i in range(len(nums)-1, -1, -1):
        #     for j in range(i+1, len(nums)):
        #         if nums[i] < nums[j]:
        #             dp[i] = max(dp[i], dp[j]+1)
        # print(dp)
        # return max(dp)

















        # dp = [1 for i in range(len(nums))]

        # for i in range(len(nums)-1, -1, -1):
        #     for j in range(i+1, len(nums)):
        #         if nums[i] < nums[j]:
        #             dp[i] = max(dp[i], 1+dp[j])
      
        # return max(dp)




        # LIS = [1 for i in range(len(nums))]

        # for i in range(len(nums)-1, -1, -1):
        #     for j in range(i+1, len(nums)):
        #         if nums[i] < nums[j]:
        #             LIS[i] = max(LIS[i], 1+ LIS[j])
        # return max(LIS)



        # LIS = [1] * len(nums)

        # for i in range(len(nums)-1, -1, -1):
        #     for j in range(i+1, len(nums)):
        #         if nums[i] < nums[j]:
        #             LIS[i] = max(LIS[i], 1 +LIS[j])
        #             # 1,10,4,5,6 <- 10을 고르면 2로 끝남, 4를 고르면 4가 3값을 가지고 있으니 1이랑 3 해서 4로 갈 수 있
        # return max(LIS)




        # LIS = [1] * len(nums)
        
        # for i in range(len(nums)-1, -1, -1):
        #     for j in range(i+1, len(nums)):
        #         if nums[i] < nums[j]:
        #             LIS[i] = max(LIS[i], 1 + LIS[j])
        # return max(LIS)
        
16700