Problem

Given an array of integers, find the length of the longest increasing subsequence in the array.
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.

Solution

# Solution:
# The solution is to use dynamic programming.
# The idea is to create a list of the same length as the input list.
# The list will contain the length of the longest increasing subsequence ending at the index of the input list.
# The list will be filled in a bottom-up manner.
# The base case is when the list is empty.
# The length of the longest increasing subsequence ending at the first index is 1.
# The length of the longest increasing subsequence ending at the second index is 1.
# The length of the longest increasing subsequence ending at the third index is 1.
# The length of the longest increasing subsequence ending at the fourth index is 2.
# The length of the longest increasing subsequence ending at the fifth index is 2.
# The length of the longest increasing subsequence ending at the sixth index is 3.
# The length of the longest increasing subsequence ending at the seventh index is 4.
# The length of the longest increasing subsequence ending at the eighth index is 4.
# The solution is the maximum value in the list.
# The time complexity is O(n^2) and the space complexity is O(n).

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

print(lengthOfLIS([10,9,2,5,3,7,101,18]))