Grokking #190

class Solution {
  public int lengthOfLIS(int[] nums) {
    ArrayList<Integer> sub = new ArrayList<>();
    sub.add(nums[0]);

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

      if (num > sub.get(sub.size() - 1)) {
        sub.add(num);
      } else {
        // Replace the first element that is greater than or equal to num in sub
        int j = 0;
        while (num > sub.get(j)) {
          j += 1;
        }

        sub.set(j, num);
      }
    }

    return sub.size();
  }
}