【GESP】C++三级练习 luogu-p1420, 最长连号

GESP三级练习，一维数组、循环分支嵌套，难度★✮☆☆☆。

luogu-P1420 最长连号

题目要求

题目描述

输入长度为 $n$ 的一个正整数序列，要求输出序列中最长连号的长度。

连号指在序列中，从小到大的连续自然数。

输入格式

第一行，一个整数 $n$。

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

输出格式

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

样例输入 #1

10
1 5 6 2 3 4 5 6 8 9

样例输出 #1

5

数据规模与约定

对于 $100\%$ 的数据，保证 $1 \leq n \leq 10^4$，$1 \leq a_i \leq 10^9$。

---

题目分析

方法一

1. 首先，读取输入的整数序列，存储在数组中。
2. 初始化一个变量 max_serial_count 来存储最长连号的长度，初始值为 1。
3. 遍历数组，使用一个内部循环来检查当前数是否是上一个数加 1，如果是，则增加当前连续数列的计数 cur_serial_count。
4. 如果不是，则重置 cur_serial_count 为 1。
5. 更新 max_serial_count 为当前最大计数和 cur_serial_count 的最大值。
6. 输出 max_serial_count 的值，即最长连号的长度。

方法二

1. 首先，读取输入的整数序列，存储在数组中。
2. 初始化一个变量 max_serial_count 来存储最长连号的长度，初始值为 1。
3. 使用一个循环来遍历数组，从第二个数开始。
4. 在循环中，检查当前数是否是下一个数减 1，如果是，则增加当前连续数列的计数 cur_serial_count。
5. 如果不是，则重置 cur_serial_count 为 1。
6. 更新 max_serial_count 为当前最大计数和 cur_serial_count 的最大值。
7. 从下一个位置继续检查即可，检查过的位置不用回溯，因此一层循环足以。
8. 输出 max_serial_count 的值，即最长连号的长度。

---

示例代码

方法一代码

#include<iostream>
#include<cmath>
using namespace std;

int main() {
    int n; // 输入的整数
    cin >> n; // 读取输入的整数
    int a[n]; // 定义一个长度为n的数组
    for (int i = 0; i < n; i++) {
        cin >> a[i]; // 读取数组元素
    }
    int max_serial_count = 1; // 初始化最大连续数列计数
    for (int i = 0; i < n; i++) {
        int last_num = a[i]; // 初始化上一个数
        int cur_serial_count = 1; // 初始化当前连续数列计数
        for (int j = i + 1; j < n; j++) {
            if (a[j] == last_num + 1) {
                cur_serial_count++; // 如果当前数是上一个数加1，则计数增加
                
            } else {
                cur_serial_count = 1; // 如果不是，则重置计数
                
            }
            max_serial_count = max(max_serial_count, cur_serial_count); // 更新最大计数
            last_num = a[j]; // 更新上一个数
        }
    }
    cout << max_serial_count; // 输出最大连续数列计数
    return 0;
}

方法二代码

#include<iostream>
#include<cmath>
using namespace std;

int main() {
    int n; // 输入的整数
    cin >> n; // 读取输入的整数
    int a[n]; // 定义一个长度为n的数组
    for (int i = 0; i < n; i++) {
        cin >> a[i]; // 读取数组元素
    }
    int max_serial_count = 1; // 初始化最大连续数列计数
    int cur_count = 1; // 初始化当前连续数列计数
    for (int i = 0; i < n; i++) {
        if (a[i + 1] == a[i] + 1) {
            cur_count++; // 如果当前数是上一个数加1，则计数增加
        } else {
            max_serial_count = max(max_serial_count, cur_count); // 更新最大计数
            cur_count = 1; // 重置计数
        }
    }
    cout << max_serial_count; // 输出最大连续数列计数
    return 0;
}

---

所有代码已上传至Github：https://github.com/lihongzheshuai/yummy-code

GESP各级别考纲要点、知识拓展和练习题目清单详见C++学习项目主页

“luogu-”系列题目已加入洛谷Java、C++初学团队，作业清单，可在线评测，团队名额有限，欢迎加入。

“bcqm-”系列题目可在编程启蒙题库进行在线评测。