目录
1.最长递增子序列
方法一:动态规划
方法二:贪心+二分查找
1.最长递增子序列
链接:. - 力扣(LeetCode)
方法一:动态规划
思路:我们定义dp[i]为最长递增子序列,那么dp[j]就是在小于i范围内的最长子序列,最长子序列最少为1,所以dp数组初始化为1.代码实行步骤如下:
这种情况下时间复杂度为O(n*2) ,空间复杂度为 O(n)
具体实现如下:
class Solution {public int lengthOfLIS(int[] nums) {int n = nums.length;int[] dp = new int[n];for(int i = 0; i < n; i++){dp[i] = 1;}int ret = 1;for(int i = 1; i < n ; i++){for(int j = 0; j < i ;j++){if(nums[j] < nums[i]){dp[i] = Math.max(dp[j] + 1,dp[i]);ret = Math.max(ret,dp[i]);}}}return ret;}
}
方法二:贪心+二分查找
思路:我们用数组来举个例子
第二种情况:(ret.get(mid) > nums[i])
这种情况下时间复杂度为nlogN(二分查找的时间复杂度为logN),空间复杂度为O(n)
代码:
public static int lengthOfLIS(int[] nums){int n = nums.length;ArrayList<Integer> ret = new ArrayList<>();ret.add(nums[0]);for (int i = 0; i < n; i++) {if(nums[i] > ret.get(ret.size() - 1)){ret.add(nums[i]);}else{int left = 0,right = ret.size() - 1;while(left < right){int mid = (left + right)/2;if(ret.get(mid) < nums[i]){left = mid + 1;}else{right = mid;}}ret.set(left,nums[i]);}}return ret.size();}