数组中最长递增子序列长度 求⼀个⼀维数组（N个元素）中的最长递增子序列的长度。 如：在序列1 ，4，2，5，3中，其最长的递增子序列为1 ，4，5或1，2，3，最长递增⼦序列的长度是3 输入说明： 第1行n为数组大小，接下来n行为数组元素

输入样例：
5
1
4
2
5
3

输出样例：
3

解题思路：
动态规划。设dp[i]为以第i个元素结尾的最长递增子序列的长度，则有状态转移方程：
dp[i] = max(dp[j])+1，其中j为所有满足nums[j]<nums[i]的位置。最后的答案即为dp数组中的最大值。
时间复杂度为O(n^2)，空间复杂度为O(n)。

Python代码：

相关问题

使用JAVA数组中最长递增子序列长度 求⼀个⼀维数组（N个元素）中的最长递增子序列的长度。 如：在序列1 ，4，2，5，3中，其最长的递增子序列为1 ，4，5或1，2，3，最长递增⼦序列的长度是3 输入说明： 第1行n为数组大小，接下来n行为数组元素

的值。

示例输入：

5
1
4
2
5
3

示例输出：

3

解题思路：

可以使用动态规划来解决这个问题。

定义dp[i]表示以第i个元素结尾的最长递增子序列的长度，那么dp[i]可以由dp[0]到dp[i-1]转移而来。

具体转移方程为：dp[i] = max(dp[j])+1，其中j是i之前的某个元素，满足a[j]<a[i]。

最后遍历整个dp数组，取最大值即为最长递增子序列的长度。

Java代码实现：

使用JAVA写一下数组中最长递增子序列长度 求⼀个⼀维数组（N个元素）中的最长递增子序列的长度。 如：在序列1 ，4，2，5，3中，其最长的递增子序列为1 ，4，5或1，2，3，最长递增⼦序列的长度是3 输入说明： 第1行n为数组大小，接下来n行为数组元素

的值。

示例输入：
5
1
4
2
5
3

示例输出：
3

解题思路：
可以使用动态规划来解决，定义状态dp[i]表示以第i个元素结尾的最长递增子序列的长度。则有状态转移方程：
dp[i] = max(dp[j])+1 (0<=j<i && nums[j]<nums[i])
即对于第i个元素，如果之前有比它小的元素nums[j]，那么以nums[i]结尾的最长递增子序列的长度就是以nums[j]结尾的最长递增子序列长度+1，取这些长度的最大值即可。最后的答案就是所有dp[i]中的最大值。

代码实现：