package question;

import java.util.Arrays;

public class Question300 {
 public static void main(String[] args) {
 int[] ints = {
 // 10, 9, 2, 5, 3, 7, 101, 18
 0, 1, 0, 3, 2, 3
 };
 System.out.println(new Question300().lengthOfLIS(ints));
 }

 public int lengthOfLIS(int[] nums) {
 int[] res = new int[nums.length];
 int len = 0;
 for (int num : nums) {
 int idx = Arrays.binarySearch(res, 0, len, num);
 idx = idx < 0 ? -idx - 1 : idx;
 res[idx] = num;
 if (idx == len) {
 len++;
 }
 }
 return len;
 }

 public int lengthOfLIS2(int[] nums) {
 int[] dp = new int[nums.length];
 Arrays.fill(dp, 1);
 for (int i = 1; i < dp.length; i++) {
 for (int j = 0; j < i; j++) {
 if (nums[i] <= nums[j]) continue;
 dp[i] = Math.max(dp[i], dp[j] + 1);
 }
 }
 int max = 0;
 for (int i = 0; i < dp.length; i++) {
 max = Math.max(max, dp[i]);
 }
 return max;
 }
}