使用JAVA写一下数组中最长递增子序列长度 求⼀个⼀维数组(N个元素)中的最长递增子序列的长度。 如:在序列1 ,4,2,5,3中,其最长的递增子序列为1 ,4,5或1,2,3,最长递增⼦序列的长度是3 输入说明: 第1行n为数组大小,接下来n行为数组元素
时间: 2024-05-20 07:16:41 浏览: 94
的值。
示例输入:
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]中的最大值。
代码实现:
相关问题
使用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代码实现:
数组中最长递增子序列长度 求⼀个⼀维数组(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代码:
阅读全文