Qual é o custo em tempo de realizar operações de busca do elemento máximo ao usar ArrayList, se os elementos são adicionados raramente?

A busca do elemento máximo em ArrayList requer percorrer todos os elementos, ou seja, tem uma complexidade temporal de O(n), onde n é o número de elementos na lista.

Se os elementos são adicionados raramente, pode-se considerar que a busca pelo máximo percorrerá toda a lista a cada vez. Para otimizar, pode-se armazenar o máximo separadamente e atualizá-lo ao adicionar novos elementos.

Exemplo de busca do máximo em ArrayList:

ArrayList<Integer> list = new ArrayList<>();
// adição de elementos
int max = Integer.MIN_VALUE;
for (int num : list) {
    if (num > max) {
        max = num;
    }
}