LeetCode 300. Longest Increasing Subsequence

Given an unsorted array of integers, find the length of longest increasing subsequence.

Example:

Input: [10,9,2,5,3,7,101,18] Output: 4 Explanation: The longest increasing subsequence is [2,3,7,101], therefore the length is 4.

Note:

There may be more than one LIS combination, it is only necessary for you to return the length.Your algorithm should run in O(n2) complexity.

Follow up: Could you improve it to O(n log n) time complexity?

找一个例子代入，观察tails数组变化的情况即可

class Solution { public int lengthOfLIS(int[] nums) { int[] tails = new int[nums.length];// tails[i]代表长度为i+1的LIS(Longest Increasing Subsequence)中结尾数字最小的一个 int size = 0; for(int num:nums){ int low = 0,high = size; //在tails数组中二分查找num,返回右边界 while(low<high){ int mid = (low+high)/2; if(num>tails[mid]){ low = mid+1; } else if(num<=tails[mid]){ high = mid; } } tails[low] = num; if(low==size){//破了 size++; } } return size; } }