public int lengthOfLIS2(int[] nums) {
        if (nums == null) return 0;
        ArrayList<Integer> list = new ArrayList<Integer>();
        for (int n : nums) {
            if (list.isEmpty() || n > list.get(list.size()-1)) {
                list.add(n);
            } else {
                int low = 0, high = list.size() - 1;
                while (low <= high) {
                    int mid = low + (high - low) / 2;
                    if (n <= list.get(mid)) {
                        high = mid - 1;
                    } else {
                        low = mid + 1;
                    }
                }
                list.set(low, n);
            }
        }
        return list.size();
    }