[Codility] Max Profit

링크 : https://app.codility.com/programmers/lessons/9-maximum_slice_problem/max_profit/start/

 

풀이 :

Max Slice 의 또 다른 변형 문제이다. 이 알고리즘의 핵심은 최선의 값을 얻을 수 있는 조건이 되는 값(minPrice)을 찾아내는 것이다. 그리고 현재의 최선의 값과 지금까지의 최선의 값을 max 로 비교하여 최종적인 최선의 값을 얻어내는 방식인 것 같다.

int solution(vector<int>& arr) 
{
    if (arr.size() == 0)
    {
        return 0;
    }

    int maxProfit = 0;
    int minPrice = arr[0];

    for (int index = 1; index < arr.size(); ++index)
    {
        int price = arr[index];

        maxProfit = max(maxProfit, price - minPrice);

        if (price < minPrice)
        {
            minPrice = price;
        }
    }

    return maxProfit;
}