Leetcode 300. Longest Increasing Subsequence

class Solution {

    // T: O(n*log(n)), S: O(n)
    public int lengthOfLIS(int[] nums) {
        if(nums == null) {
            return 0;
        }

        int n = nums.length;

        // maxSize: lengthOfLIS(Arrays.copyOfRange(nums, 0, i + 1))
        int maxSize = 0;

        int[] f = new int[n];
        Arrays.fill(f, Integer.MAX_VALUE);

        for(int i = 0; i < n; i++) {
            int insertIndex = binarySearch(f, 0, maxSize - 1, nums[i]);

            f[insertIndex] = Math.min(f[insertIndex], nums[i]);
            maxSize = Math.max(maxSize, insertIndex + 1);
        }
        return maxSize;
    }

    // return the smallest index i s.t. nums[i] >= target,
    // return endIndex + 1 if such index doesn't exists
    private int binarySearch(int[] nums, int startIndex, int endIndex, int target) {
        int li = startIndex;
        int hi = endIndex;
        while(li <= hi) {
            int mi = li + (hi - li)/2;
            if(nums[mi] >= target) {
                if(mi == li || nums[mi - 1] < target) {
                    return mi;
                }
                hi = mi - 1;
            } else {
                li = mi + 1;
            }
        }
        return endIndex + 1;
    }
}