网站建设学什么的,紧急域名升级更换通知,管理咨询公司收费,wordpress 中文名题目详情#xff1a;
给你一个整数数组 nums #xff0c;找到其中最长严格递增子序列的长度。
子序列 是由数组派生而来的序列#xff0c;删除#xff08;或不删除#xff09;数组中的元素而不改变其余元素的顺序。例如#xff0c;[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的…题目详情
给你一个整数数组 nums 找到其中最长严格递增子序列的长度。
子序列 是由数组派生而来的序列删除或不删除数组中的元素而不改变其余元素的顺序。例如[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的
子序列
。
示例 1
输入nums [10,9,2,5,3,7,101,18]
输出4
解释最长递增子序列是 [2,3,7,101]因此长度为 4 。示例 2
输入nums [0,1,0,3,2,3]
输出4示例 3
输入nums [7,7,7,7,7,7,7]
输出1提示
1 nums.length 2500-104 nums[i] 104 进阶
你能将算法的时间复杂度降低到 O(n log(n)) 吗?
代码实现
class Solution { public int lengthOfLIS(int[] nums) { // 如果数组为空则最长递增子序列的长度为0 if (nums.length 0) { return 0; } // 创建一个与输入数组等长的dp数组用于存储以当前元素结尾的最长递增子序列的长度 int[] dp new int[nums.length]; // 初始化dp数组的第一个元素为1因为每个元素本身都可以作为一个长度为1的递增子序列 dp[0] 1; // 初始化mmax为1用于记录最长递增子序列的长度 int mmax 1; // 遍历数组中的每一个元素 for (int i 1; i nums.length; i) { // 初始化dp[i]为1因为当前元素本身至少可以作为一个长度为1的递增子序列 dp[i] 1; // 遍历当前元素之前的所有元素 for (int j 0; j i; j) { // 如果当前元素大于之前的某个元素说明可以形成更长的递增子序列 if (nums[i] nums[j]) { // 更新dp[i]为当前元素与之前的元素形成的递增子序列长度与dp[i]的较大值 dp[i] Math.max(dp[i], dp[j] 1); } } // 更新mmax为dp[i]与mmax的较大值用于记录全局的最长递增子序列长度 mmax Math.max(mmax, dp[i]); } // 返回最长递增子序列的长度 return mmax; }
}
