300.py

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

Example 1:
Input: nums = [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.

Example 2:
Input: nums = [0,1,0,3,2,3]
Output: 4

Example 3:
Input: nums = [7,7,7,7,7,7,7]
Output: 1

Constraints:

1 <= nums.length <= 2500
-104 <= nums[i] <= 104
'''

# https://leetcode.com/problems/longest-increasing-subsequence/

import unittest

def longest_increasing_subsequence(nums):
    dp = [1] * len(nums)
    for i in range(len(nums)):
        for j in range(i):
            if nums[i] > nums[j]:
                dp[i] = max(dp[i], dp[j] + 1)
    return max(dp)

class TestLongestIncreasingSubsequence(unittest.TestCase):
    def test_example1(self):
        nums = [10, 9, 2, 5, 3, 7, 101, 18]
        expected = 4
        result = longest_increasing_subsequence(nums)
        self.assertEqual(result, expected)

    def test_example2(self):
        nums = [0, 1, 0, 3, 2, 3]
        expected = 4
        result = longest_increasing_subsequence(nums)
        self.assertEqual(result, expected)

    def test_example3(self):
        nums = [7, 7, 7, 7, 7, 7, 7]
        expected = 1
        result = longest_increasing_subsequence(nums)
        self.assertEqual(result, expected)

if __name__ == '__main__':
    unittest.main()