贪心算法day2（最长递增子序列）

目录

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();}