题解 | #数组中的最长连续子序列#
数组中的最长连续子序列
http://www.nowcoder.com/practice/eac1c953170243338f941959146ac4bf
排序方法，注意要去重
HashSet方法，先把所有元素放到Set里面，然后对于每一个元素做向下和向上查找，更新最大值。
import java.util.*;
public class Solution {
/**
* max increasing subsequence
* @param arr int整型一维数组 the array
* @return int整型
*/
public int MLS (int[] arr) {
// write code here
int n=arr.length;
if(n<=1){
return 1;
}
// return sortMethod(arr);
return HashSetMethod(arr);
}
public int HashSetMethod(int []arr){
HashSet<Integer> set=new HashSet<>();
int n=arr.length;
int max=0;
for(int i=0;i<n;i++){
set.add(arr[i]);
}
for(int i=0;i<n;i++){
int baseCnt=1;
int num=arr[i];
while(set.contains(num-1)){
baseCnt++;
num=num-1;
}
num=arr[i];
while(set.contains(num+1)){
baseCnt++;
num=num+1;
}
max=Math.max(max,baseCnt);
}
return max;
}
public int sortMethod(int[] arr){
Arrays.sort(arr);
int n=arr.length;
int max=0;
int temp=1;
for(int i=1;i<n;i++){
if(arr[i]==arr[i-1])
continue;
if(arr[i]==arr[i-1]+1){
temp++;
}
else{temp=1;
}
max=Math.max(temp,max);
}
return max;
}
}
