Codility MaxProfit

A vector of integers represents the price evolution of a stock share in a period. We should return the highest profit we could had buying and then selling that share.

If you have read the post about the maximum slice problem, you should see how this Codility problem could be solved in linear time, using what is commonly known as Kadane's algorithm.

Here I implemented the given test case in C++11 for GoogleTest:

TEST(MaxProfit, Given)
{
    std::vector<int> input { 23171, 21011, 21123, 21366, 21013, 21367 };
    ASSERT_EQ(356, solution(input));
}

Buying on day 0 and selling on day 1 would lead to a loss, while 1 -> 2 would give a gain of 21123 - 21011 = 112.
The best result that we could get is 21367 − 21013 = 354.

Following the max slice algorithm, I have implemented a solution in this way:

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

    int gain = 0;
    int buy = input.front();

    for(auto it = input.begin() + 1; it != input.end(); ++it) // 2
    {
        int sell = std::max(0, *it - buy); // 3
        gain = std::max(sell, gain); // 4
        buy = std::min(buy, *it); // 5
    }

    return gain;
}

1. Trivial cases, I can't get any real gain.
2. Loop on all the input elements, starting from the second one.
3. It is worthy to sell today only if we should get a positive outcome.
4. If selling today leads to the current best result, store this gain.
5. This is the key point of the algorithm. If the current stock price is lower that the previously stored one, we could get rid of that one and start using the new one.