(코딜리티) Lesson 9. [Maximum slice problem] : max_profit - python

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

MaxProfit coding task - Learn to Code - Codility

문제 내용

N개의 배열 A가 주어질 때, 0<=P<Q<N이고, A[Q] - A[P]를 해서 큰 값을 return하시오.

 

ex) A = [23171, 21011, 21123, 21366, 21013, 21367]

A[5] - A[1] = 357로 가장 큰 값이므로, 357을 return한다.

제한 사항

• N은 0~400,000
• A의 각 요소는 0~200,000

코드

def solution(A):
	
    # A가 0또는 1의 값을 가지는 경우
    if len(A) < 2:
        return 0
	
    min_price = A[0]
    m = 0
    for a in A:
        c = a - min_price
        if m < c:
            m = c
        if min_price > a:
            min_price = a

    return m

해설

조건 중에 index 순서에서 P보다 Q는 항상 커야하기 때문에, 배열 A의 제일 처음 값을 min으로 잡고, 결과를 max로 잡습니다.

 

그리고 for문을 하나씩 돌때마다, 현재 배열의 값과 min값을 비교해서 더 작은 값을 min으로 할당하고, 현재 값에 min값을 뺀 후 max값을 비교하여 할당합니다.