Compact nlogn solution using TreeSet


#1
public class Solution {
    // DO NOT MODIFY THE ARGUMENTS WITH "final" PREFIX. IT IS READ ONLY
    public int lis(final int[] A) {
        if(A.length < 2) {
            return A.length;
        }
        
        int maxLen = 1;
        TreeSet<Integer> set = new TreeSet<>();
        for(int num : A) {
            Integer next = set.ceiling(num);
            if(next != null) {
                set.remove(next);
            }
            
            set.add(num);
            maxLen = Math.max(maxLen, set.size());
        }
        
        return maxLen;
    }
}