Given an array arr[] of n non-negative integers, find the largest element in…

Concept

The maximum of a finite, non-empty sequence can be accumulated in a single left-to-right pass, because the maximum operation is associative: max(a, b, c) = max(max(a, b), c). So a running "best so far" value carries all the information from the elements already seen, and no element ever has to be revisited.

The standard form of this idea is: initialise the running best from the first element, then walk the remaining elements once and replace the running best whenever a strictly larger element appears. After the pass, the running best is the maximum of the whole sequence.

Application

1. Read n, then read the n array values.

2. Set best = arr[0]. The constraint 1 ≤ n guarantees the array is non-empty, so this first element always exists.

3. For each remaining element x, compare it with best; if x > best, assign best = x. Otherwise leave best unchanged.

4. When the pass ends, best holds the largest element. Print it.

Tracing the first example, arr[] = [1, 8, 7, 56, 90]:

The pass ends with best = 90, which is the printed answer.

Cross-check and pitfalls

• Duplicates: for [5, 5, 5, 5] the strict test x > best never fires, so best stays at 5 — correct, because equal elements cannot raise the maximum. Using >= instead would return the same value here; it changes only which position is remembered, not the maximum itself.

• Single element: for [10] the loop body never runs, and best keeps its initial value 10. This is exactly why the running best is initialised from arr[0] rather than from a placeholder.

• Initialising best = 0 happens to work only because this problem restricts arr[i] to non-negative values. On any variant that allows negative numbers it silently returns 0 for an all-negative array. Initialising from the first element is the habit that generalises.

• Complexity: the scan touches every element exactly once, so the algorithm runs in O(n) time while holding just one running value — O(1) auxiliary state beyond the elements it reads. Sorting the array and reading the last value also produces the answer, but costs O(n log n) time for no additional information.

• Input size and memory: with n as large as 106, reading the numbers costs more than comparing them. Reading the whole stream at once and splitting it — what the reference solution does — is the simplest way to stay inside the time limit, but it stores every token, so total memory grows to O(n). A reader that consumes one token at a time keeps total memory at O(1), which matters when memory rather than speed is the binding constraint. Either way, avoid a slow per-token reader, or the program can exceed the time limit even though the algorithm is optimal.