P79 最长递增子序列的长度

描述#

这个题目说的是，给你一个整数数组，你要计算数组里最长递增子序列的长度。其中，子序列不要求连续。

比如说，给你的数组 a 是：
1, 8, 2, 6, 4, 5
在这个数组里，最长的递增子序列是：
1, 2, 4, 5
因此你要返回它的长度 4。

相关视频：37. 二分搜索插入位置

代码#

public class AlgoCasts {

  // Time: O(n^2), Space: O(n)
  public int lengthOfLISDP(int[] nums) {
    if (nums == null || nums.length == 0) return 0;
    int n = nums.length, max = 1;
    int[] d = new int[n];
    d[0] = 1;

    for (int i = 1; i < n; ++i) {
      for (int j = 0; j < i; ++j) {
        int cur = nums[i] > nums[j] ? d[j] + 1 : 1;
        d[i] = Math.max(d[i], cur);
      }
      max = Math.max(max, d[i]);
    }
    return max;
  }

  private int binarySearchInsertPosition(int[] d, int len, int x) {
    int low = 0, high = len - 1;
    while (low <= high) {
      int mid = low + (high - low) / 2;
      if (x < d[mid]) high = mid - 1;
      else if (x > d[mid]) low = mid + 1;
      else return mid;
    }
    return low;
  }

  // Time: O(n*log(n)), Space: O(n)
  public int lengthOfLISBinarySearch(int[] nums) {
    if (nums == null || nums.length == 0) return 0;
    int n = nums.length, len = 0;
    int[] d = new int[n];
    for (int x: nums) {
      int i = binarySearchInsertPosition(d, len, x);
      d[i] = x;
      if (i == len) ++len;
    }
    return len;
  }

}