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)

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`);
} 
...