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

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

        int lis = 1;
        minLast[0] = nums[0];

        for (int i = 1; i < nums.length; i++) {
            int current = nums[i];

            minLast[0] = Math.min(minLast[0], current);

            for (int j = 1; j < lis; j++) {
                if (current > minLast[j - 1]) {
                    minLast[j] = Math.min(minLast[j], current);
                }
            }

            if (current > minLast[lis - 1]) {
                minLast[lis++] = current;
            }
        }

        return lis;
    }
}