Longest Natural Run
National Olympiad — Regional round (2024 season)
Submission name: rise.cpp
Problem summary
Find the longest contiguous subsequence equal to 1,2,3,… . If there is no 1, its length is zero.
Input
N, followed by N positive integers.
Output
The maximum natural-run length.
Constraints
2 < N < 1000000; each value is less than 1000000.
Worked example
An independently prepared example for this explanation.
Input
8 5 1 2 7 1 2 3 6
Output
3
Solution analysis
- Keep the length of the natural run ending at the previous position. Because a valid run begins at 1 and increases by one, its last value always equals its length.
- A new 1 starts a run of length one. Otherwise, a value equal to currentLength+1 extends a nonempty run; every other value breaks it. Update the best length after each value.
- The sample contains runs 1,2 and 1,2,3. Their lengths are two and three. The larger increasing pieces beginning at 5 or 7 are irrelevant because natural runs must start with 1.
Why it works
At each position the update preserves exactly the length of the valid natural suffix: it either starts, extends, or ceases to exist. Every natural subsequence ends somewhere, so the maximum suffix length is the answer.
Complexity: O(N) time and O(1) extra space; numbers are processed as a stream.
Watch out. The subsequence is contiguous and must start at 1. A new 1 can restart a run immediately after a break.
Commented C++17 solution
An independently written complete program with standard headers.
#include <iostream>
#include <algorithm>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
int current = 0, best = 0;
for (int i = 0; i < n; i++) {
int value;
cin >> value;
// A natural suffix ends with its own length.
if (value == 1) {
current = 1;
} else if (current > 0 && value == current + 1) {
current++;
} else {
current = 0;
}
best = max(best, current);
}
cout << best << '\n';
}