题解 | #将真分数分解为埃及分数#

代码清晰，好理解：

import java.util.*;

public class Main {
    // 其实就是最长上升子序列
    // 利用二分来查找要插入的位置
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNextInt()) {
            int numCount = in.nextInt();

            int[] nums = new int[numCount];
            for (int i = 0; i < numCount; i++) {
                nums[i] = in.nextInt();
            }

            List<Integer> ascList = new ArrayList<>();
            for (int i = 0; i < numCount; i++) {
                int target = nums[i];
                if (ascList.size() == 0 || target > ascList.get(ascList.size() - 1)) {
                    ascList.add(target);
                } else {
                    int left = 0, right = ascList.size() - 1;
                    int pos = -1;
                    while (left <= right) {
                        int mid = (left + right) / 2;
                        int searchVal = ascList.get(mid);
                        if (target == searchVal) {
                            pos = mid;
                            break;
                        } else if (target > searchVal) {
                            left = mid + 1;
                        } else {
                            // 保存右边界，让右侧更紧密，左侧更稀疏，进而左侧有更多机会寻找更小的数字
                            pos = mid;
                            right = mid - 1;
                        }
                    }
                    ascList.set(pos, target);
                }
            }

            System.out.println(ascList.size());
        }
    }
}