题解 | #最长上升子序列(一)# [S-P0]

import java.util.*;

// time O(n^2) solution.
public class Solution {
    public int LIS (int[] arr) {
      if (arr.length <= 1) return arr.length;
      
      // F(i): length of LCI ending with arr[i].
      int[] mem = new int[arr.length];
      Arrays.fill(mem, 1);
      
      // F(i) = MAX(F(j)) + 1, where j < i and arr[j] < arr[i]
      int max = 0;
      for (int i = 1; i < mem.length; i++) {
        for (int j = 0; j < i; j++) {
          if (arr[j] < arr[i]) {
            mem[i] = Math.max(mem[i], mem[j] + 1);
            // 记录global max
            max = Math.max(max, mem[i]);
          }
        }
      }
      
      return max;
    }
}