[Python 알고리즘] MaxProfit - Codility

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

---

문제 분석

주어진 배열에서 두 인덱스의 값의 차이의 최대값을 return

결과가 음수이면 0을 반환.

 

접근

배열을 탐색하면서 최솟값을 찾는다.

최솟값을 찾은 뒤에는, 더 큰 값을 만날 때마다 차이를 갱신한다.

단 result를 갱신한 뒤에, 최소값을 갱신해주자.

 

테케: [6, 3, 5, 7, 16, 1, 12, 19, 4, 5]

시간복잡도: O(N)으로 풀어야 한다. 배열의 길이가 [0...400,000].

 

풀이

def solution(A):
    result = 0
    min_value = 200001

    for i in range(len(A)):
    
        if min_value < A[i]: # 0 <= P <= Q < N일 때, A[Q] - A[P]가 양수인 경우만 판단. 음수는 어차피 0으로 반환해야 함.
            result = max(result, A[i] - min_value)
            
        min_value = min(min_value, A[i]) # 계산 이후 최솟값 갱신.

    return result