【深基4.习6】最长连号

解题思路

维护当前连续段长度 cur。若新数等于前一个数加 1，就把 cur 加一；否则重新从 1 开始。每步更新最大长度。

正确性说明

以当前位置结尾的连号段只能由前一位置连号段延伸，或者仅包含当前数，转移完全覆盖两种情况；对全部结尾取最大即可。

易错点

连号要求数值恰好加一且在原序列中相邻；不能排序；重复值会中断。

复杂度

时间 O(n)，空间 O(1)。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    long long prev = 0;
    int cur = 0, best = 0;
    for (int i = 0; i < n; i++) {
        long long x;
        cin >> x;
        if (i > 0 && x == prev + 1)
            cur++;
        else
            cur = 1;
        best = max(best, cur);
        prev = x;
    }
    cout << best << "\n";
    return 0;
}