LCS/LIS

class Solution {

    public int longestCommonSubsequence(String s1, String s2) {

        int n = s1.length(), m = s2.length();

        s1 = " " + s1; s2 = " " + s2;

        char[] cs1 = s1.toCharArray(), cs2 = s2.toCharArray();

        int[][] f = new int[n + 1][m + 1]; 

        // 因为有了追加的空格，我们有了显然的初始化值（以下两种初始化方式均可）

        // for (int i = 0; i <= n; i++) Arrays.fill(f[i], 1);

        for (int i = 0; i <= n; i++) f[i][0] = 1;

        for (int j = 0; j <= m; j++) f[0][j] = 1;

        for (int i = 1; i <= n; i++) {

            for (int j = 1; j <= m; j++) {

                if (cs1[i] == cs2[j]) {

                    f[i][j] = f[i -1][j - 1] + 1;

                } else {

                    f[i][j] = Math.max(f[i - 1][j], f[i][j - 1]);

                }

            }

        }

        // 减去最开始追加的空格

        return f[n][m] - 1;

    }

}

   public boolean increasingTriplet(int[] nums) {

        int n = nums.length, ans = 1;

        int[] f = new int[n + 1];

        Arrays.fill(f, 0x3f3f3f3f);

        for (int i = 0; i < n; i++) {

            int t = nums[i];

            int l = 1, r = i + 1;

            while (l < r) { // 二分找

                int mid = l + r >> 1;

                if (f[mid] >= t) r = mid;

                else l = mid + 1;

            }

            f[r] = t;

            ans = Math.max(ans, r);

        }

        return ans >= 3;

    }