[leetcode]Longest Increasing Subsequence

nlogn的那个太难想了... 搜索过... 具体思想是利用binary search不断去replace current number, 有大数就加进array.. 一时间没反应过来... 不过先记住这个做法 下次见到就试下
所以先写个n^2的

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19

public class Solution { public int lengthOfLIS(int[] nums) { if (nums == null || nums.length == 0){ return 0; } int lookup[] = new int[nums.length]; int max = 0; for (int i = nums.length-1; i >= 0; i--){ lookup[i] = 1; for (int j = i+1; j < nums.length; j++){ if (nums[j] > nums[i]){ lookup[i] = Math.max(lookup[i], lookup[j]+1); } } max = Math.max(max, lookup[i]); } return max; } }