# Java Simple DP O(nlogn) beats 95% java solutions

• Use an Array to store max Sequence in each step.
If the current value = pior value, keep curSeq the same.
if the current value = pior +1 (it means the sequence is continue), curSeq++
Otherwise, restart the seq.
Everytime count dp[i], get the max of curSeq and dp[i-1]

Since i used Arrays.sort, the time complexity would be O(nlogn) not O(n).

Feel free to ask questions and suggestions are welcome.

``````public class Solution {
public int longestConsecutive(int[] nums) {
Arrays.sort(nums);
int[] dp = new int[nums.length];

dp[0] = 1;
int curSeq = 1;

for(int i=1; i<nums.length; i++){
if(nums[i-1] == nums[i]){

}else if(nums[i-1]+1 == nums[i]){
curSeq ++;
}else{
curSeq = 1;
}

dp[i] = Math.max(curSeq, dp[i-1]);

}

return dp[dp.length-1];

}
}``````

• Arrays.sort(nums) is O(nlogn) so your solution is not O(N)

• Gotcha, thanks for pointing it out. But i think this is still readable and easy to understand :)

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.