Codility Tape Equilibrium

The Codility Tape Equilibrium problem is marked as "painless" in their Time Complexity section. Basically, we have a vector in input, containing at least two items, and we want to split it in a way that minimize the difference between the two sections. Our function should return such a minimal value.

A few test cases would make clearer what we are looking for:

TEST(TapeEquilibrium, Given) // 1
{
    std::vector<int> input { 3, 1, 2, 4, 3 };
    ASSERT_EQ(1, solution(input));
}

TEST(TapeEquilibrium, Couple)
{
    std::vector<int> input { 3, 3 };
    ASSERT_EQ(0, solution(input));
}

TEST(TapeEquilibrium, Couple2)
{
    std::vector<int> input { 1000, -1000 };
    ASSERT_EQ(2000, solution(input));
}

TEST(TapeEquilibrium, HundredK) // 2
{
    std::vector<int> input(100000, 1000);

    EXPECT_EQ(0, solution(input));
}

TEST(TapeEquilibrium, HundredKMinusOne)
{
    std::vector<int> input(99999, 1000);

    EXPECT_EQ(1000, solution(input));
}

1. This is the test case provided by Codility. It should be easy to see how we minimize the difference by splitting the input in {3, 1, 2} and {4, 3}. The expected output of our function is one.
2. Hundred thousand items, each of them set to one thousand. Lot of work for our function, but it is easy to see how the solution should be zero.

If you wonder, these are C++11 tests written for the GoogleTest xUnit framework. If you are using an older C++ compiler, you could have a look to a previous version of this post, that also shows a bad, O(N**2), alternative solution.

My linear time solution starts creating two partial sums, left and right, where initially the left one contains only the leftmost element, and the right one all the others. Then, I would remove one element at the time from the right one and add it to the left one. Each time I should repeat the check to see if I find a better solution.

Here is how I implemented it:

int solution(std::vector<int>& input) // 1
{
    assert(input.size() > 1); // 2

    int left = input.front(); // 3
    int right = std::accumulate(input.begin() + 1, input.end(), 0); // 4
    int result = std::abs(left - right); // 5

    std::for_each(input.begin() + 1, input.end() - 1, [&](int cur){ // 6
        left += cur;
        right -= cur;
        int tentative = std::abs(left - right);
        if(tentative < result) // 7
            result = tentative;
    });

    return result;
}

1. Actually, the input vector could and should be a const reference. Codility requirements are sometimes a bit sloppy.
2. Not required by the problem, however I felt bad to assume such a requisite without enforcing it in the code is some way.
3. Initializing the left sum is easy.
4. The right sum requires a bit more work. To keep the code more readable I used the handy STL accumulate function.
5. Initialize the function result. Notice that we are interested in the difference about left and right without caring about its sign.
6. A nice lambda function in a for_each loop keeps the code compact and, hopefully, readable. I am starting to loop from the second element, and I would end one before the end, since no section should be empty.
7. This is a better candidate, save it.