题解 | #最长上升子序列(三)#
最长上升子序列(三)
http://www.nowcoder.com/practice/9cf027bf54714ad889d4f30ff0ae5481
动态规划+二分查找，状态转移公式跟普通的有所不同，用tail数组维护当前最长的公共子序列，如果arr[i]>当前tail[len-1],则tail[len++]=arr[i],dp[i]=len; 如果不成立，则通过二分查找到最小的大于等于arr[i]的位置，插入arr[i]（这样才可以保证后面的序列尽可能长），此时注意更新dp[i]为index+1，而不是len。最后通过逆向遍历的方式就可以找到符合题意的最长上升子序列
import java.util.*;
public class Solution {
/**
* retrun the longest increasing subsequence
* @param arr int整型一维数组 the array
* @return int整型一维数组
*/
// class node{
// int cnt=0;
// List<Integer> record=new ArrayList<>();
// }
public int[] LIS (int[] arr) {
// write code here
int n=arr.length;
if(n<=1){
return arr;
}
int []tail=new int[n];
int []dp=new int[n];
dp[0]=1;
tail[0]=arr[0]; //初始化
int len=1;
for(int i=1;i<n;i++){
if(arr[i]>tail[len-1]){
tail[len++]=arr[i];
dp[i]=len;
}
else {
int index=findIndex(tail,len,arr[i]);
tail[index]=arr[i];
// len=index+1;
dp[i]=index+1;
}
}
int []res=new int[len];
for(int i=n-1;i>=0;i--){
if(len==dp[i])
res[--len]=arr[i];
}
// for(int i:dp){
// System.out.print(i+" ");
// }
// System.out.println();
// for(int i:tail){
// System.out.print(i+" ");
// }
return res;
}
public int findIndex(int[] arr,int length,int val){
int i=0,j=length-1;
while(i<j){
int mid=(i+j)/2;
if(val<=arr[mid]){
j=mid;
}
else{
i=mid+1;
}
}
return i;
}
}
查看18道真题和解析
腾讯公司福利 465人发布
