Maximum slice problem

On Codility there is a section dedicated to problems about determining the maximum slice in a vector. The generic problem, disscused in a pdf, is this:

Given a vector of integers, find the slice with the largest sum, and return that value.

An example is provided, that I converted on the spot to a C++11 GoogleTest test case:

TEST(MaxSlice, Given)
{
    std::vector<int> input { 5, -7, 3, 5, -2, 4, -1 };
    EXPECT_EQ(10, solution(input));
}

The biggest slice is the one ranging from input[2] to input[5], resulting in a sum of 10.

A quadratic solution

It shouldn't be complicated to think of a solution asymptotically quadratic in time. Loop on all the elements in the sequence. For each of them loop on all the subsequence starting there up to the input end, calculating their sums. The biggest one of them is our result.

Here is a possible implementation of this algorithm:

int solution(const std::vector<int>& input)
{
    int result = 0;
    for(unsigned i = 0; i < input.size(); ++i) // 1
    {
        int tentative = 0; // 2
        for(unsigned j = i; j < input.size(); ++j) // 3
        {
            tentative += input[j];
            result = std::max(result, tentative); // 4
        }
    }
    return result;
}

1. Check all the subsequences, defining i as their begin.
2. Store here the sum for the current subsequence.
3. Try all the possible subsequences starting from i.
4. Save the current subsequence if it is the current biggest one.

A linear solution

The previous solution works fine, but it mindlessly repeat adding on and on the same elements. We could save time just performing a single linear scan of our data, observing that when we get a negative result adding an element, it is more worthy to get rid of that subsequence, and starting from the next element:

int solution(const std::vector<int>& input)
{
    int result = 0;
    int candidate = 0;
    for(int cur : input)
    {
        candidate = std::max(0, candidate + cur); // 1
        result = std::max(result, candidate); // 2
    }

    return result;
}

1. Keep the candidate until adding the current element gives a positive value. Otherwise, reset the sequence. In the worst case, all negative input element, we won't never accept any value, and we would return the total relative to the empty subsequence, namely zero.
2. If the current candidate is a better solution, save it.

This problem is better known as maximum subarray problem, and the linear solution above was firstly found by Jay Kadane. That's way it is called Kadane's algorithm.