code_challenge_reduction_question

code_challenge_reduction_question.md

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 (written in Javascript, but I appreciate your advice in any language)

function get_best(arr) {
    var remaining = [];

    arr.forEach((current_item, i) => {
        var is_would_add = remaining.length % 2 == 0;
        var last_taken_item = remaining[remaining.length - 1];
        var next_item = arr[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) => 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 value is ${example.output.reduction} actual value is ${best_output.reduction} with remaining ${best_output.remaining}`);
    } else {
        console.log(`example ${example_index + 1} produced the expected result`);
    }
});

Some questions:

1. The solution above solves the above examples, but I challenge myself to find an example that my solution does not solve.
2. The solution above; what's its complexity?
   • what time complexity? I think it's O(N) (size of the array)
   • 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)
3. Is there another solution? Does it solve more examples, and/or perform better in terms of time complexity, or space complexity? I have some ideas:
   • 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)