Given an array, remove zero or more elements to maximize the reduction where you add odd values and subtract even values

Question

Here's a code challenge I got. (I could not solve the challenge, I ran out of time. I rephrased the challenge language and I am trying the challenge again for personal growth & computer science knowledge)

Consider an array A of N integers. You can delete zero or more of its elements.

Then take the remaining elements and reduce to an integer S according to these rules:

• elements in even positions are added
• elements in odd positions are subtracted: e.g. S = A[0] − A[1] + A[2] − A[3] + ...

Create a function to find the maximum value of S

1. When A = [4, 1, 2, 3], then S = 6, because the function could delete the third value in A: A = [4, 1, 3]. Then S = 4 − 1 + 3 = 6.
2. When A = [1, 2, 3, 3, 2, 1, 5], then S = 7, because for A = [3, 1, 5], then S is maximized S = 3 − 1 + 5 = 7.
3. When A = [1000000000, 1, 2, 2, 1000000000, 1, 1000000000], then S = 999999998, because for A = [1000000000, 1, 1000000000, 1, 1000000000], then S is maximized, S = 1000000000 -ひく 1 +たす 1000000000 -ひく1 +たす 1000000000 =わ 2999999998

You can assume that the value for S will not overflow an integer, and the length of the array (N) is under 100,000.

After giving it more thought, I tried solution function get_best.

I wrote in Javascript, but I appreciate your advice in any language.

function get_best(A) {
 // rather than modifying the original array `A`, I accumulate a new array `remaining` with only the items from `A` that I didn't "delete"
 var remaining = [];
 A.forEach((current_item, i) => {
 var is_would_add = remaining.length % 2 == 0;
 var last_taken_item = remaining[remaining.length - 1];
 var next_item = A[i + 1];
 if (is_would_add) {
 console.log(`add: the current item ${current_item} will be added (net positive); taking the current item`);
 remaining.push(current_item);
 } else {
 if (last_taken_item < current_item) {
 console.log(`subtract: last item ${last_taken_item} added *less* than the current item ${current_item} would subtract (net negative); taking the current item instead`);
 remaining.pop();
 remaining.push(current_item);
 } else if (next_item < current_item) {
 console.log(`subtract: the next item ${next_item} would be a smaller negative than the current item ${current_item}, ignoring the current item`);
 } else {
 console.log(`subtract: the current item ${current_item} wont contribute to net negative, nor would the next item be a smaller choice; taking the current item`);
 remaining.push(current_item);
 }
 }
 });
 return {
 remaining,
 reduction: remaining.reduce((accumulator, cv, ci) => {
 return accumulator + ((ci % 2 == 0) ? cv : -cv);
 }, 0)
 }
}
[
 {
 input: [4, 1, 2, 3],
 output: { remaining: [4, 1, 3], reduction: 6 }
 },
 {
 input: [1, 2, 3, 3, 2, 1, 5],
 output: { remaining: [3, 1, 5], reduction: 7 }
 },
 {
 input: [1000000000, 1, 2, 2, 1000000000, 1, 1000000000],
 output: { remaining: [1000000000, 1, 1000000000, 1, 1000000000], reduction: 2999999998 }
 }
].forEach((example, example_index) => {
 var best_output = get_best(example.input);
 if (best_output.reduction !== example.output.reduction) {
 console.warn(`example ${example_index + 1} failed, expected reduction is ${example.output.reduction} with expected remaining ${example.output.remaining} -- actual reduction is ${best_output.reduction} with actual remaining ${best_output.remaining}`);
 } else {
 console.log(`example ${example_index + 1} produced the expected result`);
 }
});

Some questions:

1. With the three examples given, did they find? I can't find better results. Of course, in answering this question, I must think about how my function should work. But I just want to confirm the examples aren't misleading!
2. The solution above solves the above examples, but I challenge myself to find an example that my solution does not solve.
3. The solution above; what's its complexity?
   • what time complexity? I think it's O(N) (size of the array A)
   • what space complexity? I'm not sure how to measure this, I'll search for some resources on understanding space complexity (I will read more of my resource for learning about complexity)
4. Are there any "tricks or techniques" you can suggest to approach this challenge even if you can't offer a solution outright?
5. Is there another solution? How is the solution better; does it solve more examples, and/or perform better in terms of time complexity, or space complexity? I have an idea, but I'm not sure if it's a good idea, or a better solution...
   • use some kind of binary search to find the maximum value, split into left and right parts, and recursively find the maximum value of each (with constraints, like the left part must have an even number of elements, etc)

• morbusg: "...You can delete zero or more of its elements." So just return the first element because you can delete the rest. ezclap
• Nate Anderson: Thanks @morbusg I agree with that, and my code does that. But what if the first value is not the largest value in the list? Then you haven't found the maximum possible value. e.g. if the second element is larger than the first... Also the challenge does not specify it, but I want to consider how my solution would behave if the list contains negative values... I guess the problem would need to specify what happens if I delete all items in the list, can I return zero?
• morbusg: My comment was a joke about the wording of the problem statement; if you delete all the other elements, it doesn't matter if there were larger integers because they're no longer there.
• Nate Anderson: Oh lol, I see now 🤣

Answer 1

You could simply use this pattern:

[greatest value, smallest value, greatest value, smallest value, ...]
 local maximum, local minimum, ...

That means, go until you found a value which is greater than the next value and if found go until you found a value which smaller than the next value. And so on. With a special treatment for the last value.

If searching for a greater value, take the last (finally add this value), if searching for a smaller value, omit this value (prevent having a value for subtraction).

With values:

[4, 1, 2, 3]
 4 1 3
[1, 2, 3, 3, 2, 1, 5]
 3 1 5
[1000, 1, 2, 2, 1000, 1, 1000]
 1000 1 1000 1 1000

The solution contains two functions for getting greater or smaller values. If one value is the greatest or smallest toggle the function to get the opposite value.

Big O

• Time complexity: a single loop with O(n) (size of the array A)
• Space complexity: another shorter array O(n), or O(1), if only the sum is used.

function getMax(values) {
 const
 smaller = (a, b) => a < b,
 greater = (a, b) => a > b,
 find = fn => (v, i, a) => {
 if (i + 1 === a.length && fn === greater || fn(v, a[i + 1])) {
 fn = fn === smaller ? greater : smaller;
 return true;
 }
 };
 return values.filter(find(greater));
}
console.log(...getMax([4, 1, 2, 3]));
console.log(...getMax([4, 1, 2, 3, 1]));
console.log(...getMax([4, 1, 2, 3, 1, 1]));
console.log(...getMax([1, 2, 3, 3, 2, 1, 5]));
console.log(...getMax([1000, 1, 2, 2, 1000, 1, 1000]));

Answer 2

The solution above solves the above examples, but I challenge myself to find an example that my solution does not solve.

Here is one example, the expected reduction is 5, but the get_best function from the original post produces an actual reduction of 4, because it subtracts the last number...

{
 input: [5, 4, 3, 2, 1],
 output: { remaining: [5], reduction: 5 }
}

My test logs output to the console that explains how my original get_best function gets it wrong:

... expected reduction is 5 with expected remaining 5,4,3,2,1 -- actual reduction is 4 with actual remaining 5,1

I can fix the get_bestfunction by adding one more else if check -- if the number would be subtracted, confirm it is not the last number from the original array A. If so, ignore it/"delete it"!

...
else if (i == A.length-1){
 console.log(`subtract: the current item is last in the list, contributes to net negative, ignoring the current item`);
} 
...

• MJ713: This is a useful insight: the final array must have an odd length. If it has an even length (>=2), then we can always increase S by dropping the last element.
• Nate Anderson: Yes that's thoughtful, thank you. That's what I realize in my answer here, where I "ignore" the last element (aka "drop it") like you suggest. But I like the way you put it, and it encourages me to think about the problem like "could the resulting array ever have zero elements in it?". (Maybe that would be necessary if the elements could be negative?... I'm not sure the original problem specifies that)
• MJ713: Actually, if we can use negative numbers, then the final array could have an even length as long as the last number is negative.
• MJ713: Also, I would argue that the result cannot be an empty array, because you cannot have a sum of no elements.
• Nate Anderson: I should read more, my challenge might be related to the maximum subarray problem -- notice some variations of the maximum subarray problem do allow an empty subarray to be summed to zero and address "non positive integers!" And there's the "max slice swap" challenge which feels even closer to my challenge because it allows a "swap" whereas my challenge allows one or more "deletes"