Найти большую парную сумму в массиве целых чисел

Question

Как найти самую большую пару в массиве положительных чисел размера n, но с целыми числами, по крайней мере, на расстоянии k? (. Например, если первый элемент является [I], то второй элемент должен быть [я + к] (или более))

Я попытался это:

int max_sum = 0; 
int sum; 
for (int i = 0 ; i < n; i++) { 
    for(int j = i + k; j < n; j++) { 
     sum = arr_sums[i] + arr_sums[j]; 
     if (sum > max_sum) { 
      max_sum = sum; 

     } 
    } 
} 

но это слишком медленный для больших массивов.

Answer 1

Это довольно просто сделать в O (n), а не O (n^2), как ваше решение.

Для каждого j, 0 ≤ j < n вычислите m [j] = "наибольший элемент от [j] до [n - 1].". Очевидно, m [n - 1] = a [n - 1], m [j] = max (a [j], m [j + 1]).

Тогда для каждого i, 0 ≤ i < n - k, вычислите [i] + m [i + k] и выберите самый большой из них.

Должно быть очевидно, как это сделать, не сохраняя при этом значения m [j] за исключением одного.

Answer 2

//assuming we checked first for n<=k 
int max_lagged = arr_sums[0]; 
int max_sum = max_lagged+arr_sums[k]; 
int sum; 
for (int i = k+1 ; i < n; i++) { 
    if (arr_sums[i-k] > max_lagged) { 
     max_lagged=arr_sums[i-k]; 
    } 
    sum = arr_sums[i] + max_lagged; 
    if (sum > max_sum) { 
     max_sum = sum; 
    } 
}