300. Longest Increasing Subsequence
題目：小猴子下山，沿著下山的路有一排桃樹酥艳，每棵樹都結(jié)了一些桃子景殷。小猴子想摘桃子，但是又一些條件需要遵守垦藏，小瘦子只能沿著下山的方向走，不能回頭伞访，每棵樹最多摘一個掂骏，而且一旦摘了一棵樹的桃子荠商，就不能再摘比這棵樹結(jié)的桃子少的樹上的桃子惠桃，那么小猴子最多能摘到幾課桃子呢？
距離說明徙缴，比如有五棵樹冒黑，分別結(jié)了10田绑，4，5抡爹，12掩驱，8棵桃子，那么小猴子最多能摘3顆桃子，來自于結(jié)了4欧穴，5民逼，12顆桃子的桃樹。
感謝futurehau大神優(yōu)秀的解析：鏈接
O(nlog(n))
算法流程：
使用一個數(shù)組h,首先令h[0]=arr[0]苔可。記已經(jīng)賦值了的h前部分為有序區(qū)缴挖，我們只考察有序區(qū)。
? 往后遍歷焚辅，對于arr[i],在h的有序區(qū)中尋找第一個大于arr[i]的位置映屋。如果找到，就把那個位置的值更新為arr[i]同蜻，否則h的有序區(qū)長度增一棚点，并且新增位置的值就為arr[i]。使用二分查找位置
?上述過程中湾蔓，從位置0到瘫析，arr[i]的更新位置的元素個數(shù)就是以arr[i]結(jié)尾的最長遞增子序列的長度。從二分查找出的位置就可以知道這個長度默责。使用一個全局變量來max存儲更新最長遞增子序列的長度贬循。
算法原理：
?h[i]表示遍歷到當(dāng)前時刻為止，長度為i+1的最長遞增子序列的最小末尾桃序。這樣其實我們每次所做的工作就是要么增加了最長遞增子序列的長度杖虾，要么就是長度不變，但是更新了每個長度對應(yīng)的最小末尾媒熊，而這有利于之后擴(kuò)展長度奇适，因為你更小嘛，我后半的元素更容易比你大芦鳍。
?這樣其實最后的h的有效區(qū)長度即為所求嚷往，但是為了不再去遍歷，中途使用一個max來記錄當(dāng)前位置時的最長遞增子序列柠衅，更新max即可皮仁。做了n次,每次二分查找位置log(n),所以復(fù)雜度為n(logn)。
public int lengthOfLIS(int[] nums) {
if(nums==null||nums.length==0)
return 0;
int[] h=new int[nums.length];
h[0]=nums[0];
int max=0;//最長子序列最右邊的位置
for(int i=1;i<nums.length;i++){
if(nums[i]>h[max]){
h[++max]=nums[i];
continue;
}
else{
int pos=findFirstBigger(h,0,max,nums[i]);
h[pos]=nums[i];
}
}
return max+1;
}
public int findFirstBigger(int[] h,int left,int right,int target){
if(left==right)
return left;
int mid=(left+right)/2;
if(h[mid]<target)
return findFirstBigger(h,mid+1,right,target);
else
return findFirstBigger(h,left,mid,target);
}
