P79. 最长递增子序列的长度

leetcode 300 lintcode 76 二分搜索 动态规划 免费 讨论

温馨提示:如果题目对您来说比较简单,可以采用 1.5 倍速观看。 立即注册观看更多视频

描述

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

比如说,给你的数组 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;
  }

}

关于 AlgoCasts

AlgoCasts 旨在用心做好每一个算法讲解视频。每个视频包含两个部分:题目的剖析讲解以及编码,力求在讲解清楚到位的基础上,尽可能地保持视频精简短小,让大家可以在碎片时间里进行学习,并收获这些算法题背后的思想与乐趣。