если массив не особо крупный, то можно остановиться на варианте с сортировкой (O(n*ln(n)) и не морочить себе голову.
а так - вариант с перебором достигает почти линейной сложности. В худшем случае это будет O(n*ln(k)), где k - сколько макс. элементов надо выбрать. Для этого надо использовать "кучу", в которой держать выбранные наибольшие элементы. Если ещё и сохранять наименьший выбранный элемент, то (когда уже выбрали k элементов), можно предварительно сравнивать с ним, тогда примерно в половине итераций кучу трогать не понадобится.