Leetcode 123. 주식 매매 의 적기 III (Python 3)

123. 주식 매매 의 적기 III
배열 을 지정 합 니 다. i 하나의 요 소 는 주어진 주식 이 제 1 위 에 있다. i 하늘의 가격.
당신 이 얻 을 수 있 는 최대 이윤 을 계산 하기 위해 알고리즘 을 설계 하 세 요.너 는 기껏해야 완성 할 수 있다. 두 몫 교역
주의: 너 는 여러 건의 거래 에 동시에 참여 할 수 없다.
예시 1:

  : [3,3,5,0,0,3,1,4]
  : 6
  :    4  （     = 0）     ，   6  （     = 3）     ，           = 3-0 = 3 。
       ，   7  （     = 1）     ，   8   （     = 4）     ，           = 4-1 = 3 。

예시 2:

  : [1,2,3,4,5]
  : 4
  :    1  （     = 1）     ，   5   （     = 5）     ,            = 5-1 = 4 。   
             1     2        ，        。   
                    ，                 。

예시 3:

  : [7,6,4,3,1] 
  : 0 
  :       ,       ,         0。

아니면 DP?

import sys
class Solution(object):
    def maxProfit(self, prices):
        """
        :type prices: List[int]
        :rtype: int
        """
        if not prices:return 0

        mp = [[[0,0]for _ in range(3)]for _ in range(len(prices))]
        mp[0][0][0], mp[0][0][1] = 0,-prices[0]
        mp[0][1][0], mp[0][1][1] = -sys.maxsize,-sys.maxsize
        mp[0][2][0], mp[0][2][1] = -sys.maxsize,-sys.maxsize

        for i in range(1,len(prices)):
            mp[i][0][0] = mp[i-1][0][0]
            mp[i][0][1] = max(mp[i-1][0][1],mp[i-1][0][0]-prices[i])

            mp[i][1][0] = max(mp[i - 1][1][0], mp[i - 1][0][1] + prices[i])
            mp[i][1][1] = max(mp[i - 1][1][1], mp[i - 1][1][0] - prices[i])

            mp[i][2][0] = max(mp[i - 1][2][0], mp[i - 1][1][1] + prices[i])

        end = len(prices) - 1
        return max(mp[end][0][0],mp[end][1][0],mp[end][2][0])

요약:
1. 상 태 는 일수, 거래 횟수, 지분 유 무 를 정의 하기 때문에 3 차원 배열 을 정의 해 야 한다.
mp [i] [j] [k] 는 i (8712 ° [0, n - 1]) 일 위치 까지 대표 하고 거래 제 j (8712 ° [0, 2] 회, 주식 유 무 (k 8712 ° [0, 1], 0 대 표 는 주식 을 가지 고 있 지 않 습 니 다. 이때 매입 할 수 있 습 니 다. 1 대 표 는 주식 을 가지 고 있 고 이때 팔 수 있 습 니 다)
2. 푸 시 방정식 (DP 방정식):                           
           mp[i][j][0]          max(mp[i-1][j][0]  ,mp[i-1][j-1][1] + prices[i])
max
           mp[i][j][1]          max(mp[i-1][j][1] , mp[i-1][j-1][0] - prices[i])            
 
대장부 표기 법: 답안 출처 참고 here

import sys
class Solution(object):
    def maxProfit(self, prices):
        """
                    :
        fstBuy:                    
        fstSell:                   
        secBuy:                   
        secSell:                   
                      ,   secSell    
           (secSell >= fstSell)
        """
        fstBuy,fstSell= -sys.maxsize,0
        secBuy,secSell= -sys.maxsize,0
        for i in prices:
            fstBuy = max(fstBuy, -i)
            fstSell = max(fstSell, fstBuy + i)
            secBuy = max(secBuy, fstSell - i)
            secSell = max(secSell, secBuy + i)
        return secSell