LeetCode 문제 풀이 기록 - 122 번 문제 (주식 매매 의 적기 2)

제목 설명
배열 을 지정 합 니 다. 그 i 번 째 요 소 는 주어진 주식 의 i 일 째 가격 입 니 다.
당신 이 얻 을 수 있 는 최대 이윤 을 계산 하기 위해 알고리즘 을 설계 하 세 요.너 는 가능 한 한 더 많은 거래 를 완성 할 수 있다.
주의: 당신 은 여러 가지 거래 에 동시에 참여 할 수 없습니다.
예시 1:
수입: [7, 1, 5, 3, 6, 4] 수출: 7 설명: 다음날 (주식 가격 = 1) 에 매입 하고 3 일 (주식 가격 = 5) 에 판매 하면 이 거래 소 는 이윤 = 5 - 1 = 4 를 얻 을 수 있다.이 어 나 흘 째 (주식 가격 = 3) 에 매입 해 5 일 째 (주식 가격 = 6) 에 팔 았 는데, 이 거래 소 는 이익 을 얻 을 수 있다 = 6 - 3 = 3.
예시 2:
수입: [1, 2, 3, 4, 5] 수출: 4 해석: 첫날 (주식 가격 = 1) 에 매입 하고 5 일 (주식 가격 = 5) 에 매각 하면 이 거래 소 는 이윤 = 5 - 1 = 4 를 얻 을 수 있다.첫날 과 다음날 잇달아 주식 을 사서 팔 지 않도록 주의해 라.여러 거래 에 동시에 참여 한 것 이기 때문에, 당신 은 다시 사기 전에 이전의 주식 을 팔 아야 합 니 다.
예시 3:
입력: [7, 6, 4, 3, 1] 수출: 0 설명: 이런 상황 에서 거래 가 완성 되 지 않 았 기 때문에 최대 이윤 은 0 이다.
사고 분석.

제목 에서 알 수 있 듯 이 여러 번 중복 구 매 할 수 있 기 때문에 우 리 는 본질 적 으로 단기 적 으로 가장 좋 고 거래 를 찾 아야 한다.예 를 들 면:

[1, 6, 7] 이런 상황 에서 최대 화 된 이윤 은 7 - 1 이지 만 우 리 는 첫날 에 사고 다음날 에 사고 다음날 에 사고 셋째 날 에 파 는 것

으로 이해 할 수 있다.

매일 가격 을 옮 겨 다 니 며 다음 호의 가격 이 지난 호 보다 크 면 result 를 업데이트 하 는 것 은 이전 단계 의 최대 화 입 니 다.

후속 거래 의 최대 치 는 최초의 거래 전제 에서 발생 하 는 것 이 아니 냐 는 질문 이 있 을 지도 모른다.저도 이런 의문 이 있 습 니 다. 예 를 들 어 [1, 3, 6, 5, 7] 이런 상황 을 살 펴 보 겠 습 니 다. 어떤 사람들 은 첫날 에 매입 한 지 5 일 만 에 판매 하면 이윤 이 가장 많 을 것 이 라 고 생각 하지만 이런 상황 은 일어나 지 않 을 것 입 니 다.다섯 번 째 날 의 값 이 m 셋째 날 이 라 고 가정 하면 이 경우 값 은 k 입 니 다.

k > m 는 고려 하지 않 아 도 이윤 의 최대 화 는 3 일 째 에 팔 린 다

.

k > = m 의 경우 첫날 매입 하고 셋째 날 판매 했다.4 일 째 매입 5 일 째 에 팔 수 있 는데 이때 이윤 이 가장 크다.그래서 규칙 을 업데이트 하 는 것 이 옳 습 니 다.

코드 구현

class Solution:
    def maxProfit(self, prices):
        """
        :type prices: List[int]
        :rtype: int
        """
        profit = 0
        if len(prices) == 0:
            return 0
        buy = prices[0]
        for j in prices[1:]:
            if j > buy:
                profit += j - buy
            buy = j
        return profit