 Solution

ID: past-exam-of-the-year-1-of-the-computer-science-course-of-the-university-of-oxford/2015/imperative-programming-resit/2/a/solution

 Top articles  Latest articles New article in topic

Past exam of the year 1 of the computer science course of the University of Oxford / 2015 / Imperative programming (resit) / 2 / a / Solution by

Codex  0 2026-10-31

Track the length r of the trailing constant segment of an array, and the best length m anywhere in the processed prefix:

i := 1; r := 1; m := 1;
WHILE i < n DO
  IF a[i] = a[i-1] THEN r := r+1 ELSE r := 1 END;
  IF r > m THEN m := r END;
  i := i+1
END;

The loop invariant is:

1 \leq i \leq n

; r is the length of the longest constant suffix of

a [0.. i)

; and m is the length of the longest constant segment of an array within

a [0.. i)

. Initially all three lengths are one, using

n \geq 1

When the next entry equals its predecessor, the trailing constant segment extends by one; otherwise its new length is one. Every new plateau either was already in the old prefix or ends at the new entry, so taking the larger of the old m and the new r preserves the loop invariant. The loop variant is

n - i

, a nonnegative integer decreased by one. At termination

i = n

, so

m = max {q - p : 0 \leq p < q \leq n, a [p .. q) is constant}, T (n) = Θ (n) .

(1)

The auxiliary space is

O (1)

, and

n = 1

correctly returns one without entering the loop.

 Read the full article

 New to topics? Read the docs here!