Editorial

Problem Summary

There are \(N\) boards at positions \(A_1 < A_2 < \cdots < A_N\). There are \(N - 1\) gaps between consecutive boards, and the \(i\)-th gap from the left has width \(A_{i+1} - A_i\). Find the index of the widest gap. If multiple gaps share the maximum width, answer the leftmost one.

Algorithm

Scan the gaps once from left to right, maintaining the largest gap width found so far (best) and its index (ans).

• Initialize best with the width of the first gap, \(A_2 - A_1\), and ans = 1.
• For \(i = 2, 3, \ldots, N - 1\), compute the width \(w = A_{i+1} - A_i\) of gap \(i\); if \(w > \text{best}\), update best and ans.

Tie-breaking

By using a strict inequality (\(>\)) as the update condition, a later gap with the same width never replaces the current answer. Since the scan proceeds left to right, the index retained is always the first (leftmost) gap achieving the maximum width — exactly what the problem requires.

Proof of Correctness

Lemma: Immediately after processing gap \(i\), ans equals the index of the leftmost widest gap among gaps \(1\) through \(i\), and best equals its width.

Proof (by induction): For \(i = 1\), ans = 1 and best = A_2 - A_1, which holds trivially since only gap 1 is considered. Assume the claim holds up to \(i - 1\), and let \(w\) be the width of gap \(i\).

• If \(w > \text{best}\): gap \(i\) is strictly wider than all of gaps \(1, \ldots, i - 1\), so the leftmost widest gap among \(1\) to \(i\) is \(i\). The update sets ans = i, best = w, and the claim holds.
• If \(w \leq \text{best}\): gap \(i\) either does not attain the maximum width or is not the leftmost one that does, so the answer is unchanged. No update occurs, and the claim holds by the inductive hypothesis.

Hence after processing \(i = N - 1\), ans is the index of the leftmost widest gap among all \(N - 1\) gaps. \(\blacksquare\)

Complexity

• Time: \(O(N)\) — each gap is examined once.
• Space: \(O(1)\) auxiliary space excluding the input array; \(O(N)\) in the implementation that stores all positions. (A true \(O(1)\)-space version keeping only the previous position is possible, but unnecessary given \(N \leq 100\).)

With \(N \leq 100\) and \(A_i \leq 10000\), this algorithm is far within the limits.