c++ - 数组中相邻元素的最大差和

Question

对于N个整数的数组，最多取出K个(不改变元素原有顺序)。函数 f 计算相邻元素之间的差异之和(考虑一下，对于给定的数字序列，f 的结果值将是 lastNumber - firstNumber ，因为中间的所有其他人都会被抵消)。工作是找出当从数组中取出任意选择的 m<=K 个数(产生一个新数组)时 f 可以具有的最大值.

因为对于 f，只有第一个和最后一个元素很重要，我的角度是涵盖这些“边界”移动的情况，对于给定的 m，比较结果并取最大值(value)。如果我正确地检查了代码，时间复杂度是 o(n^2)，但是当我将它发送给评估时，响应是“超出时间限制”。是否有更好的方法来解决这个问题，或者我是否遗漏了代码中的某些内容(我做了一些测试示例并且输出是正确的，所以我相信这是算法的问题)。

代码如下:

#include <iostream>
#include <string>


using namespace std;

int main() {

    int N, K;
    int *arr;
    int max;

    cin >> N;

    arr = new int[N];

    //Some input constraints

    if (N < 2 || N > 500000) {
        fprintf(stderr, "Los input\n");
        exit(EXIT_FAILURE);
    }

    cin >> K;


    if (K < 0 || K > N - 2) {
        fprintf(stderr, "Los input\n");
        exit(EXIT_FAILURE);
    }

    for (int i = 0; i < N; i++) {
        cin >> arr[i];
        if (arr[i] < -1000000 || arr[i] > 1000000) {
            fprintf(stderr, "Los input\n");
            exit(EXIT_FAILURE);
        }   
    }

    //The nested loop which checks boundary differences
    //depending on where the bounds are 

    max = arr[N-1] - arr[0];
    for (int i = 0; i <= K; i++) {

        for (int j = 0; j <= K - i; j++) {

            if ( max < arr[N-1-i] - arr[j])
                max = arr[N-1-i] - arr[j];
        }

    }


    cout << max << endl;
    delete [] arr;

    return 0;

}

编辑: 我试图对 Peter de Rivaz 获得线性复杂度的方法进行一番抨击。我注意到我的代码中有重复的计算。所以我决定这样做:因为端点很重要，所以我更改了外部循环，以便每次迭代时，我都会在原始数组中移动一个“间隔”(缩短一个元素)。

对于 k = 1:长度为 N - 1 的数组(原来有 2 个拟合位置)对于 k = 2:长度为 N - 2 的数组(3 个拟合..)

等等。令人惊讶的是，即使没有过度操作，仍然超过了时间限制。

#include <iostream>
#include <string>


using namespace std;

int main() {

    int N, K;
    int *arr;
    int max;

    cin >> N;

    arr = new int[N];

    if (N < 2 || N > 500000) {
        fprintf(stderr, "Los input\n");
        exit(EXIT_FAILURE);
    }

    cin >> K;


    if (K < 0 || K > N - 2) {
        fprintf(stderr, "Los input\n");
        exit(EXIT_FAILURE);
    }

    for (int i = 0; i < N; i++) {
        cin >> arr[i];
        if (arr[i] < -1000000 || arr[i] > 1000000) {
            fprintf(stderr, "Los input\n");
            exit(EXIT_FAILURE);
        }   
    }

    max = arr[N-1] - arr[0];

    for (int i = 1; i <= K; i++) {

        for (int j = 0; j <= i; j++) {

            if (max < arr[j+N-1-i] - arr[j]) 
                max = arr[j + N - 1 - i] - arr[j];

            cout << (arr[j + N - 1 - i] - arr[j]) << endl;

        }   

    }   
    cout << max << endl;
    delete [] arr;

    return 0;

}

Answer 1

如果您考虑 lastNumber 的特定值(通过从数组的右端删除 x)，那么我们将通过为 firstNumber 选择尽可能小的值来获得最大的总数。

我们已经移除了 x，所以我们最多可以从左边移除 K-x。因此，这个 x 值的最佳值来自前 K-x+1 个条目中的最小值(这些是 firstNumber 的所有可能值)。

从 x 等于 K 开始并按降序工作。

降序很有用，因为前 K-x+1 个条目中的最小值可以用前一个最小值的 O(1) 额外工作来计算。

总的来说，这会导致复杂度为 O(n)。