题解 | JAVA #二分查找 #最长上升子序列(一)# [P0-T2]

经典的LIS问题的最简形态(求LIS长度)
核心逻辑是:
  mem[n]: 长度为n+1的LIS的最后一个数的最优值(i.e. 最小).
  
有O(n^2)和O(nlogn)时间两种解。

import java.util.*;

// time O(nlogn) solution
// 视频讲解 https://www.youtube.com/watch?v=l2rCz7skAlk
public class Solution {
    public int LIS (int[] arr) {
      if (arr.length <=1 ) return arr.length;

      // mem[i]: 长度为i+1的LIS的最后一个数的最优值(i.e. 最小).
      // LIS.length<=arr.length, 所以就用arr.length去初始
      int[] mem = new int[arr.length];
      // 初始: LIS = { arr[0] }
      mem[0] = arr[0];
      int lenLIS = 1;
      
      for (int i = 1; i < arr.length; i++) {
        int num = arr[i];
        // search for num in mem[0, lenLIS-1]
        // note: mem[0, lenLIS-1] is already sorted
        // 请务必参照Arrays.binarySearch的documentation
        // 我只能说用Java刷题的咱们都是上辈子折翼的天使
        int result = Arrays.binarySearch(mem, 0, lenLIS, num);
        
        // result>=0表示found，那么插不插入都一样
        if (result >= 0) continue;
        
        // else，result = -insertionPoint - 1
        int insertionPoint = -1-result;
        mem[insertionPoint] = num;  // replace
        // num大于mem[0, lenLIS-1]里的所有数, 
        // i.e. 之前的replace其实是个append, 所以lenLIS++
        if (insertionPoint == lenLIS) lenLIS++;
      }
      
      return lenLIS;
    }
}

import java.util.*;

// time O(n^2) solution
public class Solution {
    // dp[i]: length of LIS ending at i.
    //  = MAX{ dp[j] + 1 }, for j < i && arr[j] < arr[i]
    public int LIS (int[] arr) {
      int[] dp = new int[arr.length];
      Arrays.fill(dp, 1); // dp[i] is at least 1, i.e. 1 element
      int maxLen = 0;
      
      for (int i = 0; i < arr.length; i++) {
        for (int j = 0; j < i; j++) {
          if (arr[j] < arr[i]) {
            dp[i] = Math.max(dp[i], dp[j]+1); 
          }
        }
        maxLen = Math.max(maxLen, dp[i]);
      }
      
      return maxLen;
    }
}