Interval Diversity

모든 시작점 $l$을 고정하고, 끝점 $r$을 $l$부터 $N$까지 하나씩 늘려 보자.

현재 구간에 들어 있는 값들의 등장 횟수를 저장하면, $A_r$을 새로 추가할 때 이 값이 이전에 등장하지 않았는지 확인할 수 있다. 이전에 등장하지 않았다면 서로 다른 정수의 개수 $x$를 $1$ 증가시킨다.

각 구간의 길이는 $y=r-l+1$이므로, 모든 구간에 대해 $x^2/y$를 계산하여 최댓값을 갱신하면 된다.

구간의 개수는 $O(N^2)$개이고 각 갱신은 평균 $O(1)$에 할 수 있으므로 전체 시간 복잡도는 $O(N^2)$이다.