Sum of differences of adjacent elements in an array

Question

For an array of N integers, at most K will be taken out (without changing the original order of elements). A function f calculates the sum of differences between adjacent elements (when thought about, for a given sequence of numbers, the result value of f will be lastNumber - firstNumber, because all the others in between will get canceled out). The job is to find out the maximum value that f can have of the newly constructed array when an arbitrary choice of m<=K numbers get taken out of the original array (resulting in a new array).

Example: A = 1 7 2 5 3 8 2 3 6 5 5 , K = 4 Solution is 5. So, for some m (in range of 0 to K) some m numbers get taken out, giving a new array. Function f deals with that array.

Since for f, only the first and the last element matter, my angle was to cover the cases when these "bounds" shifted, for the given m, compare the results and take the greatest value. If I examined the code correctly, the time complexity is \$o(n^2)\$, but when I sent it over for evaluation, the response was "Time Limit Exceeded". Is there a better approach to this problem or did I miss something in my code (I made a few test examples and the outputs were correct, so it's a matter of algorithm, I believe)?

Here is the code:

#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

General implementation

• using namespace std; is considered bad practice and should be avoided.
• The C++ style std::cin and std::cout are used for input and output, but the C style fprintf is used for error reporting. Maybe choose one style for consistency (e.g. use std::cerr for errors)?
• The whole array arr could as easily be replace by a std::vector<int>, letting the container take care of bookkeeping and memory cleanup.

Algorithm

Your algorithm uses (as you correctly stated) \$O(K^2)\$ time by calculating all possible combinations. This can be reduced to \$O(K)\$ with a bit of cleverness:

As far as I understand it, the problem basically boils down to: f = last - first, maximize f by removing up to m <= K total elements. This means to maximize f, one needs to find how many elements to remove from each "end" of the array, because as you correctly deduced, only those matter.

Now we can step from one end up to K elements in, and for each step calculate the change in f if we were to remove elements up to this point. If it's the best result so far, we note it for the current position, else we note the previous better result (after all, we always can take less elements away). We do this for both ends.

Then we can add the noted values for taking x elements from the front and K-x elements from the back together (so up to K elements total), and find the maximum for this value. This value is the highest increase possible for f.

Adding this value to the previously calculated original value of f gives us then the maximum value for f.

Step by step

Let's take your example: A = [1 7 2 5 3 8 2 3 6 5 5] , K = 4.

Let B = [? ? ? ? ?] be the map x elements removed from the front -> max increase of f so far.

• If we were to remove m = 0 elements from the front, f wouldn't change. B = [0 ? ? ? ?].

• If we were to remove m = 1 element from the front, f would change by 1 - 7 = -6. This is worse than removing 0 elements, so we store the result for that instead (after all, we can always remove less elements for a better result). B = [0 0 ? ? ?].

• If we were to remove m = 2 elements from the front, f would change by 1 - 2 = -1. Since this is again worse than removing nothing (our best result so far), let's store that again, B = [0 0 0 ? ?].

• Same results for m = 3 (1 - 5 = -4) and m = 4 (1 - 3 = -2) respectively (so final B = [0 0 0 0 0]).

Let's do this again with C = [? ? ? ? ?], but now we remove elements from the back.

• If we were to remove m = 0 elements from the back, nothing changes. C = [0 ? ? ? ?].

• If we were to remove m = 1 elements from the back, nothing would change (5 - 5 = 0). C = [0 0 ? ? ?].

• If we were to remove m = 2 elements from the back, f would increase by 6 - 5 = 1. This is better than previous results, so we store that. C = [0 0 1 ? ?].

• If we were to remove m = 3 elements from the back, f would change by 3 - 5 = -2. This is worse than our best result (1) so far, so let's store that instead. C = [0 0 1 1 ?].

• If we were to remove m = 4 elements from the back, f would change by 2 - 5 = -3, so let's again store the best result so far. C = [0 0 1 1 1].

Now we can go over both B and C and look what the best results for removing up to x elements from the front and K - x (so m <= x + (K - x) = K) elements from the back.

• x = 0: The best result we could get by removing up to 0 elements from the front and K elements from the back is B[0] + C[K] = 0 + 1 = 1.
• x = 1: The best result we could get by removing up to 1 elements from the front and K-1 elements from the back is B[1] + C[K-1] = 0 + 1 = 1.
• x = 2: B[2] + C[K-2] = 0 + 1 = 1.
• x = 3: B[3] + C[K-3] = 0 + 0 = 0.
• x = 4: B[4] + C[K-4] = 0 + 0 = 0.

So the best we could get is an increase of f by 1 (by removing 0 elements from the front and 2 elements from the back, though that wasn't asked).

Algorithm code

In code (using arrays for consistency with existing code):

/* other stuff, like reading arr, up to this statement */
max = arr[N-1] - arr[0];

auto frontRemovals = new int[K+1]; // B
auto backRemovals = new int[K+1]; // C
auto maxFront = = frontRemovals[0] = 0;
auto maxBack = baxkRemovals[0] = 0;

for(auto frontIndex = 1, backIndex = N-2; frontIndex <= K; ++frontIndex, --backIndex) {
    if(arr[0] - arr[frontIndex] > maxFront) {
        maxFront = arr[0] - arr[frontIndex];
    }
    frontRemovals[frontIndex] = maxFront;

    if(arr[backIndex] - arr[N-1] > maxBack) {
        maxBack = arr[backIndex] - arr[N-1];
    }
    backRemovals[frontIndex] = maxBack;
}

auto maxDifference = 0;
for(auto x = 0; x <= K; ++x) {
    if(frontRemovals[x] + backRemovals[K - x] > maxDifference) {
        maxDifference = frontRemovals[x] + backRemovals[K - x];
    }
}

max += maxDifference;
/* printing result, freeing array, etc. */

Note: With a bit more cleverness, this operation can be done in one pass. However, this exercise is up to the reader ;)