Longest Increasing Subsequence LeetCode solution in Java

1
class Solution {
2
  public int lengthOfLIS(int[] nums) {
3

4
    ArrayList<Integer> lis = new ArrayList<>();
5

6
    for (int num : nums) {
7

8
      int size = lis.size();
9

10
      if (size == 0 || size > 0 && num > lis.get(size - 1)) {
11
        lis.add(num);
12
      } else {
13
        int insertIndex = bs(lis, num);
14
        lis.set(insertIndex, num);
15
      }
16
    }
17

18
    return lis.size();
19
  }
20

21
  int bs(List<Integer> list, int target) {
22
    int lo = 0;
23
    int hi = list.size() - 1;
24

25
    while (lo < hi) {
26
      int mid = (lo + hi) / 2;
27
      if (list.get(mid) < target) {
28
        lo = mid + 1;
29
      } else {
30
        hi = mid;
31
      }
32
    }
33
    return lo;
34
  }
35
}