这里参考网上的一种写法,使用差分数组,将一个数组的每一个元素减去前一个元素,结果送入另外开辟的一个数组d[i],之后,如果d[i] == 1, 那么这两个数据就是连续的。
具体思路:首先读入数据,同时将差分数组计算出来,之后循环遍历数组,这里的i < n + 1,至于为什么,下面会有解释,如果d[i] == 1,说明前后两个数据是连续的,不等于1,说明不连续,同时更新ans(最大连续个数),同时将s = 0(当前连续个数)
i < n + 1 的原因:针对下面这个数据
20
3 5 6 2 3 4 5 6 8 9 10 11 12 13 14 15 16 17 18 19
如果写成i < n; 那么答案是5 显然是不对的,原因是当i = 20的时候 循环自动退出,就不会更新ans,(这个时候的s是11),所以要将在比较一次才可以。
还有最后要输出ans+ 1,因为第一个数字也包含在连续序列中。
代码#includeusing namespace std; int a[100005]; int d[100005]; int main() { int n; int ans = 1;//ans是当前最大的连续数个数 int s = 0; //s 是当前有几个连续的数 cin>>n; // 20 // 3 5 6 2 3 4 5 6 8 9 10 11 12 13 14 15 16 17 18 19 //对于这个数据 要注意最后一个数字19 结束之后直接退出循环,就没有更新ans 导致ans = 5 for(int i = 1; i <= n; i++) { scanf("%d",&a[i]); d[i] = a[i] - a[i - 1];//将差值结果记录于数组中 } for(int i = 1; i <= n + 1; i++) { if(d[i] == 1) { s++;//如果两个数的差值为1 也就是连号 当前数量加一 } if(d[i] != 1) { if(s > ans) { ans = s;//更新ans 遇到不连号的 } s = 0;//同时令s = 0 } } if(ans > 1) { //加一 的原因:比如 0 2 3 4 这里的2 d[1] = 2 但是他也是连续数列中的一个 cout<<(ans + 1); } else { cout<<1; } return 0; }
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)