Lesson 7: MaxProfit (Max Profit)

Lesson 7: MaxProfit
https://codility.com/programmers/lessons/7

This problem indeed can be translated as a `max-slice' problem.

Notice that the profit/loss in two consecutive days is the price difference between these days. If we buy the stock at the first day and then sell it on the second day, the profit/loss of these two days is the price difference between these days.

Now let's think that we buy the stock at the first day and then sell it on the third day. The profit/loss between these two days is the price difference between these days. However, it can be also considered that the profit/loss between the first day and the third day is the price difference between the first day and the second day + the price difference between the second day and the third day.

So this problem can be translated to find the max-profit from the sequence of the price differences between a day and its next day.

This strategy gives the 100% score.

int solution(int A[], int N) 
{
    int max_ending = 0;
    int max_slice  = 0;

    int i;
    
    for (i = 1; i < N; i++){
        int diff = A[i] - A[i - 1];
        int tmp = max_ending + diff;
        max_ending = tmp < 0 ? 0 : tmp;
        max_slice  = max_slice < max_ending ? max_ending : max_slice;
    }

    return max_slice;
}