Алгоритм поиска в массиве двух максимальных значений

В результате нужно получить индексы ячеек массива с максимальными значениями.
Например, для массива arr[4, 50, 11, 20] это будут 1 и 3 (arr[1], arr[3]) - индексы максимальных значений.

Ответ

Ну, почему бы не пробежаться по массиву и держать текущие k наибольших значений?
Вот вам псевдокод:
list maximalK = empty // инвариант: maximalK содержит отсортированный список наибольших // k из всех просмотренных элементов foreach e in sourceList p = position of e in maximalK // (binary search) if (p >= k) continue insert e into maximalK at position p if maximalK.size > k remove last from maximalK
Заметьте, что при k == sourceList.size вы получаете просто алгоритм сортировки (бинарными) вставками.
Временная сложность: O(n * k) (n — размер списка), за счёт сдвига при вставке. (Используя sorted map для maximalK, можно уменьшить до O(n * log k).)