题解 | #数组中的最长连续子序列#

//使用动态规划，时间复杂度O(n)
int MLS(vector<int>& arr) {
// write code here
sort(arr.begin(), arr.end());
int dp[arr.size()];
for(int i = 0; i<arr.size();i++)
{
dp[i] = 1;
}
int max = 0;
for(int i = 1; i < arr.size(); i++)
{
if(arr[i] == arr[i-1] + 1)
{
dp[i] = dp[i-1]+1;
}
else if(arr[i] == arr[i-1])
{
dp[i] = dp[i-1];
}
if(max < dp[i]) max = dp[i];
}
return max;</int>