GESP C++
3级
练习题
最长连号

最长连号

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

luogu-P1420 最长连号

题目要求

题目描述

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

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

输入格式

第一行，一个整数 nn。

第二行，nn 个整数 aia_i，之间用空格隔开。

输出格式

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

样例输入 #1 

10
1 5 6 2 3 4 5 6 8 9

样例输出 #1 

5

数据规模与约定

对于 100%100\% 的数据，保证 1≤n≤1041 \leq n \leq 10^4，1≤ai≤1091 \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 custom/custom-post-content-inner.html %}

示例代码

方法一代码 

#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;
}

{% include custom/custom-post-content-footer.md %}

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

“luogu-”系列题目可在 洛谷题库 在线评测。

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

GESP/CSP 认证学习微信公众号
GESP/CSP 认证学习微信公众号
Last updated on
白细胞计数小鱼比可爱