题目：最长上升子序列

• 给定一个无序的整数数组，找到其中最长上升子序列的长度。

示例:

输入: [10,9,2,5,3,7,101,18]
输出: 4 
解释: 最长的上升子序列是[2,3,7,101]，它的长度是 4。

说明:

• 可能会有多种最长上升子序列的组合，你只需要输出对应的长度即可。
• 你算法的时间复杂度应该为O(n^2)。
• 进阶: 你能将算法的时间复杂度降低到O(n logn)吗?

来源：力扣（LeetCode）第300题

链接：https://leetcode-cn.com/problems/longest-increasing-subsequence

分析：

• 非常好的一道题目
• 可以使用动态规划来解决。
• 除了最常规的一种方法外还有另一种动态规划的方法，使用二分查找的思想。
• 具体可以看看搜索插入位置(LeetCode第35题)
• 动态规划：
  • 设1个状态表示到这个数为止，最长上升子序列是多少。
  • 然后遍历数组，当遍历到第i个状态时，查看在dp中到第i个数为止已经有多长了，那么你只要在右边找到比当前数大的值，然后在它的dp数组下加上1。
  • 最后找到dp数组中最大的值，就是答案。
• dp + 二分查找：
  • 我们遍历数组，将每个数放进dp数组中。
  • 由于dp数组是单调递增的，所以可以使用二分查找找到插入的位置。
  • 有两种情况，如果找到了这个值，那么直接覆盖就行了，如果没找到这个值，那么将比它大的最小的值覆盖。其实就是插入位置。

代码：

• dp

  class Solution {
  public int lengthOfLIS(int[] nums) {
      int len = nums.length;
      int[] dp = new int[len];
      Arrays.fill(dp, 1);
      for (int i = 0; i < len; i++) {
          for (int j = i + 1; j < len; j++) {
              if (nums[i] < nums[j]) dp[j] = Math.max(dp[j], dp[i] + 1);
          }
      }
      int ans = 0;
      for (int i = 0; i < len; i++) ans = Math.max(ans, dp[i]);
      return ans;
  }
  }
  

• dp + 二分

  class Solution {
  private int len;
  private int[] dp;
  public int lengthOfLIS(int[] nums) {
      len = nums.length;
      dp = new int[len];
      Arrays.fill(dp, Integer.MAX_VALUE);
      for (int i = 0; i <len; i++) dp[find(nums[i])] = nums[i];
      int ans = 0;
      for (int i = 0; i <len; i++) {if (dp[i] != Integer.MAX_VALUE) ++ans;}
      return ans;
  }
  
  public int find(int val) {
      int left = 0, right = len - 1;
      while (left <= right) {
          int mid = right + (left - right >> 1);
          if (dp[mid] == val) {
              return mid;
          } else if (dp[mid] < val) {
              left = mid + 1;
          } else {
              right = mid - 1;
          }
      }
      return left;
  }
  }