Codility Mushroom Picker

We have a street with mushroom at every place, represented by a non-empty and potentially big (one hundred thousand) vector of relatively small unsigned integers (say, less than one thousand). It is given also the initial position of a picker, and its movement range. We want to maximize the number of collected mushrooms.

This problem is proposed as example in the Codility Prefix Sum section. I would argue it is not the best choice, since the prefix sum part of the problem is hidden by the complexity of the determining how the picker moves in the array. Still, I had some good fun solving it.

Test cases

There is no codility check for this problem, so I wrote an awful lot of test cases, trying to check all the possible cases that come to my mind. I spare you the pain of seeing them, still I suggest you to spend some time thinking on them. Here is the Codility given one (C++11, GoogleTest):

int solution(const std::vector<unsigned>& input, unsigned pos, unsigned moves);

TEST(MushroomPicker, Given)
{
    EXPECT_EQ(25, solution({ 2, 3, 7, 5, 1, 3, 9 }, 4, 6));
}

I have seven mushroom places, the picker starts its trip on position 4, it could moves up to 6 consecutive places. Its best strategy would be to start moving to the left up to the third cell, than move to the right till the end of the array. In this way we would add up to 25 mushrooms.

An inefficient solution

Let's not care for the moment about performance. Try to focus instead of which intervals we have to check.
Theoretically, we could change direction any time we like, however It is easy to see how we should not change it more than once.

My idea is to start moving the picker to the left for a while, then change its direction and move it to the right.
I simply won't care of doing the same starting moving to the right, counting on the symmetry of the problem:

int solution(const std::vector<unsigned>& input, unsigned pos, unsigned moves)
{
    assert(!input.empty()); // 1
    assert(pos < input.size());

    unsigned result = 0; // 2

    unsigned maxLeftShift = std::min(pos, moves); // 3
    for(unsigned curLeftShift = 0; curLeftShift <= maxLeftShift; ++curLeftShift) // 4
    {
        unsigned first = pos - curLeftShift; // 5
        unsigned rightShift = std::min(pos + (moves - curLeftShift * 2), unsigned(input.size() - 1)); // 6
        unsigned last = std::max(pos, rightShift); // 7

        unsigned tentative = 0;
        for(unsigned i = first; i <= last; ++i) // 8
        {
            tentative += input[i];
        }
        result = std::max(result, tentative); // 9
    }

    return result;
}

1. Ensuring requisites as stated in the problem.
2. Currently fetched mushrooms.
3. I check the initial picker position and the number of moves available to get the maximum number of moves to the left. I want to be sure I won't break the vector boundary.
4. The left shift would range from zero (no shift at all, go directly to the right) up to the maximum value calculated in (3).
5. The current sub-interval starts at the initial picker position opportunely shifted to the left.
6. This is a bit tricky. Once we have moved to the left, we should determine which movement we are still allowed to do on the right. Getting back to the original position would cost the left shift doubled. And we have also to ensure that we won't break the right vector boundary.
7. And (6) is not enough. We have to consider also that our sub-interval should have at least its right limit in the initial picker position.
8. Given all the above, how it is just a matter of picking up all the mushroom in the [first, last] interval.
9. If the current sub-interval is richer that the previous ones, store it as temporary solution.

I have spent large part of the time writing lines (6) and (7), the rest of the code shouldn't be a problem.
Performance-wise, this implementation has an obvious problem, represented by the (8) loop.

Linear solution

Instead of recalculating each time the mushroom sum for a specific sub-interval, we could calculate the partial sum for the complete interval once and for all, outside the main for-loop.

I have already talked about partial sum, and its C++ STL implementation, in a previous post. Please, have a look at that post for more info.

It is not difficult to refactor the previous solution using partial sum (some code cleanup as bonus):

int solution(const std::vector<unsigned>& input, unsigned pos, unsigned moves)
{
    assert(!input.empty());
    assert(pos < input.size());

    std::vector<unsigned> parSum(input.size()); // 1
    std::partial_sum(input.begin(), input.end(), parSum.begin());

    unsigned result = 0;
    for(unsigned i = 0; i <= std::min(pos, moves); ++i)
    {
        unsigned first = pos - i;
        unsigned last = std::max(pos, std::min(pos + (moves - i * 2), unsigned(input.size() - 1)));
        result = std::max(result, first ? parSum[last] - parSum[first - 1] : parSum[last]); // 2
    }

    return result;
}

1. Create a partial sum from the input. We should expect this sort of transformation:
{2, 3, 7, 5, 1, 3, 9} -> {2, 5, 12, 17, 18, 21, 30}
2. If our sub-interval starts on the first vector element, we want to check simply the partial sum for its last element. Otherwise, we want subtract from it the partial sum for the elements on the left of the sub-interval.