O $(n^2)$
public int lengthOfLIS(int[] nums) {
if (nums.length == 0) return 0;
int[] dp = new int[nums.length];
Arrays.fill(dp, 1);
int max = 1;
for (int i = 1; i < nums.length; i++) {
//iterate from the beginning
for (int j = 0; j < i; j++) {
if (nums[i] > nums[j]) {
//update if we've seen longer subsequence
dp[i] = Math.max(1 + dp[j], dp[i]);
}
max = Math.max(max, dp[i]);
}
}
return max;
}
/*
1 7 3 5 9 12 ans = 5
1 1 1 1 1 1
1 2 1 1 1 1
1 2 2 1 1 1
1 2 2 3 1 1
1 2 2 3 4 1
1 2 2 3 4 **5**
*/
O($nlogn$)
public int lengthOfLISBinarySearch(int[] nums) {
List<Integer> list = new ArrayList<>();
for (int num : nums) {
int pile = Collections.binarySearch(list, num); //returns position
if (pile < 0) pile = ~pile; // -10 -> 9 (invert bits) pile = Math.abs(pile) - 1
if (pile == list.size()) {
list.add(num);
} else {
list.set(pile, num);
}
}
return list.size();
}