Python 알고리즘 문제 풀이(feat. Code Kata)

문제
prices는 배열이며, 각 요소는 매일의 주식 가격입니다. 만약 한 번만 거래할 수 있다면 = 사고 팔 수 있다면, 제일 큰 이익은 얼마일까요?

예를 들어,

Input: [7,1,5,3,6,4]
Output: 5
Input: [7,1,5,3,6,4]
Output: 5
설명: 2일(가격=1)에 샀다가 5일(가격=6)에 사는 것이 6-1이라 제일 큰 수익 7-1=6 은 안 되는거 아시죠? 먼저 사야 팔 수 있습니다.

Input: [7,6,4,3,1]
Output: 0
Input: [7,6,4,3,1]
Output: 0
설명: 여기서는 매일 가격이 낮아지기 때문에 거래가 없습니다. 그래서 0

풀이 접근 방식

1. 주식 특성 상 먼저 사야 팔 수 있음을 고려
2. 싸게 사고 산 가격보다 비싸게 팔아야 함을 고려
3. 그렇다면 맨 뒤에서부터 앞의 값을 빼면 가장 큰 이익을 구할 수 있음

내 풀이 코드

def maxProfit(prices):
    output = []
    for i in range(len(prices)-1,-1,-1):                 (1)
      for j in range(i-1,-1,-1):
        output.append(prices[i]-prices[j])               (2)

    if max(output) < 0:                                  (3)
      return 0
    else:
      return max(output)                                 (4)

풀이 설명

(1) 배열의 가장 뒤쪽부터 하나씩 앞으로 오면서 반복문을 지정
(2) 뒤의 값에서 앞의 값을 빼주어 output 배열에 append 시킴
(매도-매수 차이가 이익이므로 뒤에서 앞의 값을 빼줌)
(3) 만약 모든 차의 값이 0보다 작으면 팔 수 없으므로 이익의 결과값은 0
(4) 차의 값이 0보다 크면 output에서 이익이 가장 큰 값을 반환해줌