题解 | JAVA #最长上升子序列(二)# [P0]

就是(一)的O(nlogn)解
https://blog.nowcoder.net/n/dae14ef8bd484b01b541da73a155d9a2

import java.util.*;

public class Solution {
    public int LIS (int[] a) {
      if (a.length <= 1) return a.length;
      
      int[] mem = new int[a.length];
      mem[0] = a[0];
      int lenLIS = 1;
      
      for (int i = 1; i < a.length; i++) {
        int num = a[i];
        // search mem[0, lenLIS-1]
        int result = Arrays.binarySearch(mem, 0, lenLIS, num);
        if (result >= 0) continue;  // found, skip
        
        // result = -insertionPoint - 1
        int insertionPoint = -1-result;
        mem[insertionPoint] = num;
        if (insertionPoint == lenLIS) lenLIS++;
      }
      
      return lenLIS;
    }
}