最长上升子序列（Python and C++解法）

题目：

给定一个无序的整数数组，找到其中最长上升子序列的长度。

示例:

输入: [10,9,2,5,3,7,101,18]
输出: 4
解释: 最长的上升子序列是 [2,3,7,101]，它的长度是 4。
说明:子序列不同于子串，可以不连续。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/longest-increasing-subsequence

思路：

　　采用动态规划。

　　定义状态：dp[i] 表示以 nums[i] 这个数为结尾的最长递增子序列的长度。那么最终结果（子序列的最大长度）应该是 dp 数组中的最大值。

　　状态转移：如果要形成一个新的最长递增子序列，那么只需要找到那些结尾比当前数值小的子序列中的最长的一个，然后把当前数值加在后面，此时需要注意，新的最长子序列的长度+1。

Python解法：

 1 class Solution:
 2     def lengthOfLIS(self, nums: List[int]) -> int:
 3       Len = len(nums)
 4       if Len == 0:
 5         return 0
 6       dp = [1] * Len  # 子序列的最短长度是1
 7       for i in range(Len):
 8         for j in range(i):
 9           if nums[j] < nums[i]:
10             dp[i] = max(dp[i], dp[j]+1)
11       maxLen = 1
12       for i in range(Len):
13          if dp[i] > maxLen:
14            maxLen = dp[i]
15       return maxLen

C++解法：

 1 class Solution {
 2 public:
 3     int lengthOfLIS(vector<int>& nums) {
 4       int Len = nums.size();
 5       if(Len == 0)
 6         return 0;
 7       vector<int> dp(Len, 1);  // 子序列的最短长度是1
 8       for(int i = 0; i < Len; i++) {
 9         for(int j = 0; j < i; j++)
10           if(nums[j] < nums[i])
11             dp[i] = max(dp[j]+1, dp[i]);
12       }
13       int maxLen = 1;
14       for(int i = 0; i < Len; i++)
15         if(dp[i] > maxLen)
16           maxLen = dp[i];
17       return maxLen;
18     }
19 };