// Solution: LIS
// The original problem is a LCS (Longest common subsequence) problem that can be solved in O(n*m) time.
// Since the elements in the target array is unique, we can convert the numbers into indices that helps to reduce the problems to LIS (Longest increasing subsequence) that can be solved in O(mlogn) time.
// e.g.
// target:[6,4,8,1,3,2] => [0, 1, 2, 3, 4, 5]
// array:[4,7,6,2,3,8,6,1] => [1,-1, 0, 5, 4, 2, 0, 3] => [1, 0, 5, 4, 2, 3]
// and the LIS is [0, 2, 3] => [6, 8, 1], we need to insert the rest of the numbers.
// Ans = len(target) - len(LIS)
// Time complexity: O(mlogn)
// Space complexity: O(n)
class Solution {
    public int minOperations(int[] target, int[] arr) {
        Map<Integer, Integer> m = new HashMap<Integer, Integer>();
        for (int i = 0; i < target.length; ++i)
            m.put(target[i], i);
        List<Integer> s = new ArrayList<Integer>();
        for (int a : arr) {
            Integer mit = m.get(a);
            if (mit == null) continue; // 注意对象才能判断是否为null。
            final int idx = mit;
            int it = lower_bound(s, idx, 0, s.size());
            if (it == s.size())
                s.add(idx);
            else
                s.set(it, idx);
        }
        return target.length - s.size();
    }
    private int lower_bound(List<Integer> A, int val, int l, int r) {
        while (l < r) {
            int m = l + (r - l) / 2;
            if (A.get(m) >= val)
                r = m;
            else
                l = m + 1;
        }
        return l;
    }
}

@@ -1,12 +1,15 @@
+// 
 // Solution:
@@ -7,17 +7,765 @@
 Solution
-:
+ 1: LCS (TLE)%0A// // LCS is a clasic DP problem that can be solved in the following time/space.%0A// // Time complexity: O(mn)%0A// // Space complexity: O(mn) -%3E O(min(n, m))%0A// class Solution %7B%0A//     public int minOperations(int%5B%5D target, int%5B%5D arr) %7B%0A//         int m = target.length, n = arr.length;%0A//         int%5B%5D%5B%5D dp = new int%5Bm + 1%5D%5Bn + 1%5D;%0A//         for (int i = 1; i %3C m + 1; ++i)%0A//             for (int j = 1; j %3C n + 1; ++j)%0A//                 dp%5Bi%5D%5Bj%5D = Math.max(dp%5Bi - 1%5D%5Bj%5D,%0A//                            Math.max(dp%5Bi%5D%5Bj - 1%5D,      // %E6%B3%A8%E6%84%8F%E4%B8%89%E7%9B%AE%E8%BF%90%E7%AE%97%E7%AC%A6%E5%A4%96%E9%9D%A2%E5%8A%A0%E6%8B%AC%E5%8F%B7%EF%BC%8C%E4%B8%8D%E7%84%B6%E4%BC%9A%E8%BF%90%E8%A1%8C%E9%94%99%E8%AF%AF%EF%BC%8C%E5%AF%BC%E8%87%B4%E7%AD%94%E6%A1%88%E4%B8%8D%E5%AF%B9%E3%80%82%0A//                                     dp%5Bi - 1%5D%5Bj - 1%5D + (target%5Bi - 1%5D == arr%5Bj - 1%5D ? 1 : 0)));%0A//         return m - dp%5Bm%5D%5Bn%5D;%0A//     %7D%0A// %7D%0A%0A// Solution 2: Reduce to
  LIS%0A// 

update MinimumOperationstoMakeaSubsequence.java