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