MaxProfit

🔗 문제 링크

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

❔ 문제 설명

An array A consisting of N integers is given. It contains daily prices of a stock share for a period of N consecutive days. If a single share was bought on day P and sold on day Q, where 0 ≤ P ≤ Q < N, then the profit of such transaction is equal to A[Q] − A[P], provided that A[Q] ≥ A[P]. Otherwise, the transaction brings loss of A[P] − A[Q].

For example, consider the following array A consisting of six elements such that:

A[0] = 23171
A[1] = 21011
A[2] = 21123
A[3] = 21366
A[4] = 21013
A[5] = 21367

If a share was bought on day 0 and sold on day 2, a loss of 2048 would occur because A[2] − A[0] = 21123 − 23171 = −2048. If a share was bought on day 4 and sold on day 5, a profit of 354 would occur because A[5] − A[4] = 21367 − 21013 = 354. Maximum possible profit was 356. It would occur if a share was bought on day 1 and sold on day 5.

Write a function,

def solution(A)

that, given an array A consisting of N integers containing daily prices of a stock share for a period of N consecutive days, returns the maximum possible profit from one transaction during this period. The function should return 0 if it was impossible to gain any profit.

For example, given array A consisting of six elements such that:

A[0] = 23171
A[1] = 21011
A[2] = 21123
A[3] = 21366
A[4] = 21013
A[5] = 21367

the function should return 356, as explained above.

⚠️ 제한사항

• N is an integer within the range [0..400,000];

• each element of array A is an integer within the range [0..200,000].

---

💡 풀이 (언어 : Python)

풀이가 까다로웠다. 풀이의 아이디어는 최소값 변수를 하나 선언하고 for문을 한번 돌면서 최소 변수를 계속 갱신해주고 오는 숫자들의 최소값과의 차이의 최대값도 변수를 선언해서 계속 갱신해준다. 시간복잡도는 $O(N)$

def solution(A):
    maxProfit = 0
    minStock = A[0]
    # 길이 0인 케이스 처리
    if len(A) == 0:
        return 0
    
    for a in A[1:]:
        if a < minStock:
            minStock = a
        else:
            profit = a - minStock
            if maxProfit < profit:
                maxProfit = profit

    return maxProfit