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;

? ? }