LeetCode-3.14-300-M- 最长上升子序列(Longest Increasing Subsequence)
程序员文章站
2024-01-22 11:06:58
...
给定一个无序的整数数组,找到其中最长上升子序列的长度。
示例:
输入: [10,9,2,5,3,7,101,18]
输出: 4
解释: 最长的上升子序列是 [2,3,7,101],它的长度是 4。
说明:
可能会有多种最长上升子序列的组合,你只需要输出对应的长度即可。
你算法的时间复杂度应该为 O(n2) 。
进阶: 你能将算法的时间复杂度降低到 O(n log n) 吗?
思路
(1)动态规划。
解法1-动态规划
class Solution {
public int lengthOfLIS(int[] nums) {
int len = nums.length;
if (len < 2) {
return len;
}
int[] dp = new int[len];
Arrays.fill(dp, 1);
for (int i = 1; i < len; i++) {
for (int j = 0; j < i; j++) {
if (nums[j] < nums[i]) {
dp[i] = Math.max(dp[i], dp[j] + 1);
}
}
}
int res = 0;
for (int i = 0; i < len; i++) {
res = Math.max(res, dp[i]);
}
return res;
}
}
作者:jyd
链接:https://leetcode-cn.com/problems/longest-increasing-subsequence/solution/zui-chang-shang-sheng-zi-xu-lie-dong-tai-gui-hua-2/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。
解法2-动态规划+二分
class Solution {
public int lengthOfLIS(int[] nums) {
int[] tails = new int[nums.length];
int res = 0;
for(int num : nums) {
int i = 0, j = res;
while(i < j) {
int m = (i + j) / 2;
if(tails[m] < num) i = m + 1;
else j = m;
}
tails[i] = num;
if(res == j) res++;
}
return res;
}
}
上一篇: tensorflow入门-mnist手写数字识别(一)
下一篇: TensorFlow 手写数字识别
推荐阅读
-
LeetCode-3.14-300-M- 最长上升子序列(Longest Increasing Subsequence)
-
最长上升子序列(LIS: Longest Increasing Subsequence)
-
【dp-LIS】牛客网 --最长上升子序列 POJ 2533--Longest Ordered Subsequence(LIS模板题)
-
最长递增子序列(Longest Increasing Subsequence)
-
最长上升子序列(LIS: Longest Increasing Subsequence)
-
最长上升子序列 Longest Increasing Subsequence 输出其中一个序
-
Longest Increasing Subsequence最长增长子序列
-
LeetCode 题解之 300. Longest Increasing Subsequence(最长上升子序列 LIS)