查找整数数组中最大的两个数之和

Question

如何在一个大小为n的正整数数组中找到距离至少为k的最大对值？（例如，如果第一个元素是a[i]，那么第二个元素应该是a[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;

        }
    }
}

但对于大型数组而言，它的速度过慢。

- Mitsos101

---

数组已排序吗？ - frodo

int max_sum; --> int max_sum = INT_MIN; 因为您使用了一个未初始化的变量。 - Weather Vane

@WeatherVane 抱歉，我的错误，应该是0。 - Mitsos101

边界情况警告！在一组数字中，两个数字之和的最大值可能是负数。 - Oka

@Oka 我又犯错了，整数总是正数。 - Mitsos101

那么它们为什么不是“无符号的”？ - Weather Vane

Answer 1

在O(n)的时间复杂度下实现非常简单，不像你的解决方案一样是O(n²)。

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. 

毋庸置疑，应该很明显如何在不实际存储除一个值外的m [j]的情况下完成此操作。

- gnasher729

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

- Matt Timmermans

---

难道不应该是 n>=k 吗？ - Mitsos101