定义dp[i]表示前i个元素组成的数组的最长上升子序列长度，转移方程为dp[i] = max(dp[i-1], dp[j]+1) 其中j<i且nums[j]<nums[i]

定义dp[i]表示以第i个元素结尾的最长上升子序列长度，转移方程为dp[i] = 1 + max{ dp[j] | j < i 且 nums[j] < nums[i] }，无满足条件的j时dp[i]=1

定义dp[i]表示以第i个元素结尾的最长上升子序列长度，转移方程为dp[i] = nums[i] > nums[i-1] ? dp[i-1]+1 : 1

该线性动态规划解法的时间复杂度为O(n)，空间复杂度为O(n)