给定一个无序的整数数组，找到其中最长上升子序列的长度。
发布时间
阅读量：
阅读量
On December 6, 2020, the problem falls under the LeetCode platform with a medium difficulty rating: Longest Increasing Subsequence (https://leetcode-cn.com/problems/longest-increasing-subsequence/).
一、题目描述
给定一个无序的整数数组，找到其中最长上升子序列的长度。
示例:
输入: [10,9,2,5,3,7,101,18]
输出: 4
解释: 最长的上升子序列是 [2,3,7,101]，它的长度是 4。
代码解释二、解题思路
解题思路：单击此处访问最长递增子序列问题详细解析页面
三、实现代码
实现代码如下：
public class Leetcode300 {
public static void main(String[] args) {
int[] nums = {10,9,2,5,3,7,101,18};
System.out.println(lengthOfLIS(nums));
}
public static int lengthOfLIS(int[] nums) {
if (nums.length == 0){
return 0;
}
int[] dp = new int[nums.length];
for (int i = 0; i < dp.length; i++) {
//将所有数字初试状态置为1
dp[i] = 1;
}
for (int i = 1; i < dp.length; i++) {
for (int j = 0; j < i; j++) {
if (nums[i] > nums[j]){
dp[i] = Math.max(dp[i],dp[j]+1);
}
}
}
int max = 1;
for (int i = 0; i < dp.length; i++) {
max = Math.max(max,dp[i]);
}
return max;
}
}
代码解释全部评论 (0)
还没有任何评论哟~