题解 | #最长上升子序列(三)# [P2]

就是(一)的衍生 需要多一个mem2记录每个数在以它结尾的LIS中的index。
看懂了(一)的O(nlogn)解这个基本也就懂了。

import java.util.*;

public class Solution {
    public int[] LIS (int[] arr) {
      if (arr.length <= 1) return arr;
      
      // mem[i]: 长度为i+1的LIS的最后一个数的最优值(i.e. 最小).
      int[] mem = new int[arr.length];
      // mem2[i]: length-1 of the LIS ending with arr[i].
      int[] mem2 = new int[arr.length];
      
      // 初始， LIS = { arr[0] }
      mem[0] = arr[0];
      int lenLIS = 1;
      mem2[0] = 0;
      
      for (int i = 1; i < arr.length; i++) {
        int num = arr[i];
        // search mem[0, lenLIS-1]
        int insertionPoint = Arrays.binarySearch(mem, 0, lenLIS, num);
        
        // 如果insertionPoint是正的那就不需要调整
        if (insertionPoint < 0) {
          // 如果是负的, insertionPoint = -insertionPoint - 1
          insertionPoint = -1-insertionPoint;
          mem[insertionPoint] = num;
          // 如果insertion是个append，需要跟新LIS长度。
          if (insertionPoint == lenLIS) lenLIS++;
        }
        // 以arr[i]结尾的LIS的(长度-1)就是insertionPoint
        mem2[i] = insertionPoint;
      }
      
      int[] ans = new int[lenLIS];
      for (int i = arr.length-1; i >= 0; i--) {
        if (mem2[i] == lenLIS - 1) {
          ans[lenLIS - 1] = arr[i];
          lenLIS--;
        }
      }
      return ans;
    }
}