Find largest pair sum in array of integers

Question

How can I find the largest pair sum in an array of positive integers of size n, but with the integers at least at a distance k? (For example, if the first element is a[i], then the second element should be a[i+k] (or more).)

I tried this:

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;

        }
    }
}

but it's too slow for large arrays.

Answer 1

It's quite simple to do in O (n), not O (n²) like your solution.

For each j, 0 ≤ j < n, 
calculate m [j] = "largest element from a [j] to a [n - 1]. ". 
Obviously m [n - 1] = a [n - 1], m [j] = max (a [j], m [j + 1]). 

Then for each i, 0 ≤ i < n - k, calculate a [i] + m [i + k], 
and pick the largest of these. 

It should be obvious how to do this without actually storing the values m [j] except for one.

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;
    }
}