링크 : 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;
}
'취미 > Programming Problems' 카테고리의 다른 글
[HackerRank] DFS: Connected Cell in a Grid (0) | 2023.06.05 |
---|---|
[HackerRank] Breadth First Search: Shortest Reach (0) | 2023.06.01 |
[Codility] Max Slice Sum (0) | 2023.05.06 |
[Codility] Equi Leader (0) | 2023.05.06 |
[Codility] Passing Cars (0) | 2023.05.03 |