/*
Runtime: 1 ms, faster than 92.68% of Java online submissions for Longest Increasing Subsequence.
Memory Usage: 36.8 MB, less than 73.00% of Java online submissions for Longest Increasing Subsequence.
*/
class Solution {
    public int lengthOfLIS(int[] nums) {
        if (nums.length == 0) return 0;
        if (nums.length == 1) return 1;

        int[] minLast = new int[nums.length];

        int lis = 0;

        for (int current: nums) {
            int idx = Arrays.binarySearch(minLast, 0, lis, current);
            if (idx >= 0) continue;

            int insertionPoint = -idx - 1;
            minLast[insertionPoint] = current;

            if (insertionPoint == lis) {
                ++lis;
            }
        }

        return lis;
    }
}