Maximum Forward Difference
National Olympiad — National round (2026 season)
Submission name: dif.cpp
Problem summary
Choose two positions i < j whose values satisfy a[j] > a[i]. Find the largest possible value of a[j] − a[i]. The order of the positions must be preserved.
Input
N, followed by N positive integers.
Output
The largest positive forward difference.
Constraints
2 ≤ N ≤ 1,000,000; 1 ≤ a[i] < 100,000. At least one valid pair exists.
Worked example
An independently prepared example for this explanation.
Input
5 9 2 6 1 5
Output
4
Solution analysis
- Imagine choosing the right endpoint j. The best left endpoint is the smallest value seen strictly before j.
- Read the first number into minimumEarlier. For every later value, compare value − minimumEarlier with the best answer, then update the running minimum. The sequence never needs to be stored.
- For 9, 2, 6, 1, 5, the useful improvements are 6 − 2 = 4 and 5 − 1 = 4. The answer is 4. Using the overall maximum 9 and minimum 1 would incorrectly give 8 because 9 comes first.
Why it works
For a fixed right endpoint, subtracting the smallest earlier value maximizes the difference among all legal left endpoints. Taking the maximum of those best choices over every right endpoint examines the best pair implicitly.
Watch out. This is not simply max(array) − min(array). Update the answer using an earlier value, then update the minimum. The existence guarantee makes an initial answer of 0 safe.
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 count, minimumEarlier;
cin >> count >> minimumEarlier;
int bestDifference = 0;
for (int i = 1; i < count; i++) {
int value;
cin >> value;
// minimumEarlier comes only from positions before this one.
bestDifference = max(bestDifference, value - minimumEarlier);
minimumEarlier = min(minimumEarlier, value);
}
cout << bestDifference << '\n';
}