题解 | #数组中的最长连续子序列#
数组中的最长连续子序列
http://www.nowcoder.com/practice/c6b19ebae63143baa7fbb5b6d8dc24ec
//本题题目要求的是时间复杂度为NlogN，空间复杂度为N
//很明显就是先排序然后动态规划求最长序列
//用这种方法实现代码如下.本题还有时间复杂度为N空间复杂度N的更好解法
#include<bits/stdc++.h>
using namespace std;
int main(){
int n;
cin>>n;
int *arr=new int[n];
for(int i=0;i<n;i++)
cin>>arr[i];
sort(arr, arr+n);//默认从小到大排序，想从大到小排自己写比较方法
//排完序之后暴力解就是每次都遍历一遍数组找最长子序列时间复杂度为N²，不满足要求
//所以采用动态规划
int dp[n];//dp数组的含义为dp[i]表示以arr[i]结尾的最长连续子序列长度
dp[0]=1;
int res=1;
for(int i=1;i<n;i++){
if(arr[i]==arr[i-1]+1){//此时最长子序列加1
dp[i]=dp[i-1]+1;
res=res>dp[i]?res:dp[i];
}
else if(arr[i]==arr[i-1])
dp[i]=dp[i-1];
else
dp[i]=1;
}
cout<<res<<endl;
return 0;
}
//很明显就是先排序然后动态规划求最长序列
//用这种方法实现代码如下.本题还有时间复杂度为N空间复杂度N的更好解法
#include<bits/stdc++.h>
using namespace std;
int main(){
int n;
cin>>n;
int *arr=new int[n];
for(int i=0;i<n;i++)
cin>>arr[i];
sort(arr, arr+n);//默认从小到大排序，想从大到小排自己写比较方法
//排完序之后暴力解就是每次都遍历一遍数组找最长子序列时间复杂度为N²，不满足要求
//所以采用动态规划
int dp[n];//dp数组的含义为dp[i]表示以arr[i]结尾的最长连续子序列长度
dp[0]=1;
int res=1;
for(int i=1;i<n;i++){
if(arr[i]==arr[i-1]+1){//此时最长子序列加1
dp[i]=dp[i-1]+1;
res=res>dp[i]?res:dp[i];
}
else if(arr[i]==arr[i-1])
dp[i]=dp[i-1];
else
dp[i]=1;
}
cout<<res<<endl;
return 0;
}
