在整数数组中找到最大的对

Question

如何在大小为n的正整数数组中找到最大的对,但是整数至少在距离k？(例如,如果第一个元素是[i],那么第二个元素应该是[i + k](或更多).)

我试过这个:

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,计算a [i] + m [i + k],并选择其中最大的一个.

显而易见的是,如果不实际存储除m之外的值m [j],如何做到这一点.