//Given an unsorted array of integers, find the length of longest increasing subsequence.
//For example,
//Given [10, 9, 2, 5, 3, 7, 101, 18],
//The longest increasing subsequence is [2, 3, 7, 101], therefore the length is 4. Note that 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?
1.給出O(n2)的時間復雜度算法
public int lengthOfLIS(int[] nums) {
int dp[]=new int[nums.length];
dp[0]=1;
int max=1;
for(int i=1;i<dp.length;i++){
int maxValue=0;
for(int j=0;j<i;j++){
if(nums[i]>nums[j]){
maxValue=Math.max(maxValue, dp[j]);
}
}
dp[i]=maxValue+1;
max=Math.max(max, dp[i]);
}
return max;
}
2.用二分查找給出O(nlogn)算法
image.png
public int longestSequence(int[] a){
int[] sub=new int[a.length];
int length=0;
for(int ele:a){
int index=binarySearch(sub,ele,length);
sub[index]=ele;
if(index==length){
length++;
}
}
return length;
}
private int binarySearch(int[] sub, int data, int length) {
int l=0;
int r=length;
while(l<r){
int mid=l+(r-l)/2;
if(sub[mid]==data){
return mid;
}
else if(sub[mid]>data){
r=mid;
}
else{
l=mid+1;
}
}
return l;
}
