MaxProfit

코딜리티

• N개의 배열 A가 주어질 때, 0<=P<Q<N이고, A[Q] - A[P]를 해서 큰 값을 return하시오.
• N은 0~400,000
• A의 각 요소는 0~200,000

---

접근 방식

: for문을 돌려서 해당 인덱스+1부터 끝까지의 배열의 원소 중 가장 큰 수와 해당 원소의 차이를 구하여 max함수로 비교하여 저장. -->O(N^2)으로 시간초과

알게된점

모든 원소에 대해 비교 작업을 할 필요 없이,

• 가장 작다고 설정한 원소보다 작으면 업데이트
• 가장 작다고 설정한 원소보다 크면 차이를 구하고 비교

def solution(A):

    if len(A) < 2:
        return 0
    
    j = A[0]
    maxi = 0
    for i in range(1, len(A)):
        tmp = A[i] - j
        if maxi < tmp:
            maxi = tmp
        if j > A[i]:
            j = A[i]
    return maxi