Есть ли более быстрый способ найти наибольшую пару из int []?

Question

Есть ли другой способ использования java Collection, который делает этот код быстрее?Есть ли другой способ сделать этот код быстрее?Является ли ArrayList правильным выбором для такого рода проблем?

import java.util.*;

class Main{

public static int GetHighestPairSum(int[] L)
{
    int largest = L[0];
    int index = 0;
    int secondlargest = L[0];

    ArrayList<Integer> I = new ArrayList<Integer>();

    for (int i = 0; i<L.length; i++)
    {
        I.add(L[i]);

        if (i == 0)
        {
            largest = L[i];
        }
        else 
        {   
            if (largest < L[i])
            {
                largest = L[i];
                index = i;
            }
        }
    }

    I.remove(index);
    secondlargest = Collections.max(I);

    return largest + secondlargest;
}

public static void main(String[] args) {

     int[] testarr = new int[] {1,2,3,23,67,100,2,11,3,2,6,7,1,13,4,7,9,34,7,3,2,1,100}; 
     System.out.println(GetHighestPairSum(testarr));
}

}

Answer 1

С этой реализацией вам придется дважды просматривать список.Более эффективный подход состоял бы в том, чтобы хранить две переменные для самого большого и второго по величине элементов и обновлять их обе по мере необходимости.Обратите внимание, что это может быть сделано путем итерации массива напрямую, и нет необходимости копировать его в ArrayList, как предполагает ответ @ GBlodgett.

Аналогичное решение, которое может поддерживать любое количество элементов, может использовать[PriorityQueue]:

public static int getHighestTuppleSum(int[] arr, int n) {
    PriorityQueue<Integer> pq = new PriorityQueue(arr.length);
    for (int i : arr) {
        if (pq.size() < n) {
            pq.add(i);
        }
        if (pq.peek() < i) {
            pq.poll();
            pq.add(i);
        }
    }
    return pq.stream().mapToInt(Integer::intValue).sum(); 
}