洛谷网校题解之【 P1420 最长连号】

编程入门行业动态更新时间:2024-10-10 08:22:48

题目描述

输入n个正整数，（1<=n<=10000),要求输出最长的连号的长度。（连号指从小到大连续自然数）

输入输出格式

输入格式：

第一行，一个数n;

第二行，n个正整数，之间用空格隔开。

输出格式：

一个数，最长连号的个数。

输入输出样例

输入样例#1： 复制

10
3 5 6 2 3 4 5 6 8 9

输出样例#1： 复制

链接：luogu./problemnew/show/P1420

代码实现（已AC）

（相比大神们的代码，我的小白代码显得十分庸俗……但是学习是一个进步的过程，只有写出自己的东西，再参考其他大神的解法以及思路，这样可以在学习中进步，虚心学习，细水长流，积沙成塔。）

#include<iostream>
#include<algorithm>
#include<cstdio>

using namespace std;
#define N 10000
bool cmd(int a,int b) //布尔函数（从大到小排序）
{
return a>b;
}

//主函数

int main()
{
int t[N]={0},a[N],n,i,j,k; //t[N]为数组，记录从当前下标位置起，从小到大连续自然数的个数
cin >> n; //输入n的值，即数组大小
for(i=0;i<n;i++)
cin >> a[i];
for(i=0;i<n;i++)
{
j=i; //记录当前下标i
k=j+1; //从i+1位置开始比较
if(a[j]+1==a[k])
{
do{ //进入循环，找从小到大连续自然数的个数
if(a[j]+1==a[k])
{
t[i]++; //如果满足条件，对应的数组位置加一
j++;
k++;
}
else break; //一旦不满足条件，则结束当前循环
}while(k<=n);
}
}
for(i=0;i<n;i++) //这里是判断所有数据相等的情况
{
if(t[i]!=0)
break;
}
if(i==n)
t[0]=1; //如果数组中所有的数据都是相等的，那么此时的输出结果为1
else
{
for(i=0;i<n;i++)
{
if(t[i]!=0)
t[i]+=1; //由于在记录时，只是针对当前的数字之和有几个满足连续的上升自然数序列，因此如果有满足的数，结果 //需要加一，即加上当前的数
}
}

sort(t,t+n,cmd); //标记的数组进行排序，并输出最大的元素
cout << t[0];
return 0;
}

接下来，分享一篇来自大神的DP代码：（链接）luogu./blog/cys2004a/solution-p1420

#include<iostream>
using namespace std;
int main()
{int n;cin>>n;int a[n+1],dp[n+1];for(int i=1;i<=n;i++){cin>>a[i];}int maxn=0;for(int i=n;i>0;i--){if(i==n){dp[i]=1;}else{if(a[i+1]-1==a[i]){dp[i]=dp[i+1]+1;}else{dp[i]=1;}}maxn=max(dp[i],maxn);}cout<<maxn;return 0;
}