Lesson 9: Maximum Slice Problem → Max Profit

문제

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

MaxProfit coding task - Learn to Code - Codility

---

문제 풀이

리스트의 값 들은 주식의 가격을 나타내고, 인덱스는 날짜이다.

주식을 산 후에 특정 날짜에 판매하였을 때 가장 큰 이득을 반환하면 된다.

이득이 없는 경우(마이너스) 에는 0을 반환한다.

---

코드

def solution(A):
    if len(A) < 2:
        return 0

    max_profit = None
    min_price = A.pop(0)

    for price in A:
        cur_profit = price - min_price
        if price < min_price:
            min_price = price

        if max_profit is None:
            max_profit = cur_profit
        else:
            max_profit = max(max_profit, cur_profit)

    return max_profit if max_profit > 0 else 0

• 브루트 포스로 풀게 되면 O(N^2)의 시간 복잡도를 가지게 된다.

• 최소값과 현재 값을 비교하여 최대 이익이 발생하는지 확인하면 O(N)의 시간 복잡도로 문제를 풀 수 있다.