采用动态规划的方式求解

求解最长上升子列的问题，可以转化为求解输入的序列num中，分别以每一个元素作为结尾的序列的最长子列的问题。第i个元素的子列最长长度，等于满足nums[j] < nums[i]的子列的最长长度+1。

具体求解步骤如下：

1. 取列表dp，长度等于输入的序列长度n。dp[i]代表以num[i]结尾的序列的最长长度，初始化为1。
2. 递归关系式：dp[i]就等于满足nums[j] < nums[i] & 0<= j< i条件的dp[j]+1与dp[i]取最大值。
3. 通过两层循环使得i遍历range(1, n), j遍历range(0, i)更新所有的dp值。

def lengthOfLIS(n, nums):
        if not nums:
            return 0
        dp = [1 for _ in range(n)]
        for i in range(1, n):
            for j in range(i):
                if nums[j] < nums[i]:
                    dp[i] = max(dp[i], dp[j] + 1)
        return max(dp)

n = int(input()) # 输入数组长度
s = input().split(" ") # 输入代表数组的字符串
nums = [int(s[i]) for i in range(len(s))]
print(lengthOfLIS(n, nums))