Given an array A[0]...A[n-1] of integers, find out the length of the longest ascending subsequence.

Assumptions

• A is not null

Examples
Input: A = {5, 2, 6, 3, 4, 7, 5}
Output: 4
Because [2, 3, 4, 5] is the longest ascending subsequence.

Solution 1: dp[i]: 直到第i个数的longest ascending subsequence (including i)。对每个i，检查所有j < i，若a[j] < a[i],

dp[i] = Math.max(dp[i], dp[j] + 1)

  public int longest(int[] array) {
    if (array.length == 0) {
      return 0;
    }
    int[] dp = new int[array.length];
    int max = 1;
    for (int i = 0; i < dp.length; i++) {
      dp[i] = 1;
      for (int j = 0; j < i; j++) {
        if (array[j] < array[i]) {
          dp[i] = Math.max(dp[i], dp[j] + 1);
        }
      }
      max = Math.max(max, dp[i]);
    }
    return max;
  }

Solution 2: 用一个list维持递增的序列。先往list加入a[0]，然后从i = 1开始，如果a[i]大于list最后一个元素，往list加入a[i]，否则找到list中第一个比a[i]大的数，把它设为a[i]，最后返回list.size()。用binary search

  public int longest(int[] array) {
    if (array.length == 0) {
      return 0;
    }
    List<Integer> ascending = new ArrayList<>();
    ascending.add(array[0]);
    int max = 1, index = 0;
    for (int i = 1; i < array.length; i++) {
      if (array[i] > ascending.get(ascending.size() - 1)) {
        ascending.add(array[i]);
      } else {
        int firstLarger = search(ascending, array[i]);
        ascending.set(firstLarger, array[i]);
      }
    }
    return ascending.size();
  }
  private int search(List<Integer> list, int target) {
    int start = 0, end = list.size() - 1;
    while (start + 1 < end) {
      int mid = start + (end - start) / 2;
      if (list.get(mid) <= target) {
        start = mid + 1;
      } else {
        end = mid;
      }
    }
    if (list.get(start) > target) {
      return start;
    }
    return end;
  }