leetcode 121. 주식 을 매매 하 는 가장 좋 은 시기 [동태 계획] [배열] [Easy]

제목:
배열 을 지정 합 니 다. i 하나의 요 소 는 주어진 주식 제 이다. i 하늘의 가격.
만약 당신 이 최대 한 건의 거래 (즉, 주식 을 매입 하고 판매 하 는 것) 만 허용 한다 면, 당신 이 얻 을 수 있 는 최대 이윤 을 계산 하 는 알고리즘 을 설계 하 세 요.
주식 을 사기 전에 주식 을 팔 아 서 는 안 된다 는 것 을 주의해 라.
예시 1:

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

예시 2:

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

생각:
        문 제 는 뒤의 수 치 를 찾 아 앞 수치의 최대 차 이 를 줄 이 는 셈 이다.첫 번 째 방법 은 2 층 for 순환 이 하나씩 줄 어 들 고 시간 복잡 도 는 O (n) 이다.²)。효율 이 너무 낮 습 니 다. 두 번 째 방법 은 동적 계획 의 사상 에 활용 되 었 습 니 다. 최대 이윤 을 요구 합 니 다. 먼저 배열 을 옮 겨 다 닐 때 현재 주식 가격 의 최소 치 와 현재 이윤 의 최대 치 를 보존 하고 이 두 가 지 를 순서대로 업데이트 해 야 합 니 다. 옮 겨 다 니 기 가 끝 난 후에 현재 최대 이윤 치 를 되 돌려 주면 됩 니 다.
       예 를 들 어 현재 이윤 의 최대 치 는 maxpro 이 고 현재 최소 주식 가격 은 minPrice 입 니 다.
        현재 주식 가격 은 prices [i] 이 고 판단 해 야 할 것 은:
        첫째, min = min > prices[i] ? prices[i] : min
        둘째, maxpro = maxpro < prices [i] - min? prices[i] - min : maxpro
코드:

class Solution(object):
    def maxProfit(self, prices):
        """
        :type prices: List[int]
        :rtype: int
        """
        if prices == None or len(prices) < 0:
            return None
        if len(prices) == 0:
            return 0
        maxpro,minPrice = 0,prices[0]
        for item in prices:
            if item < minPrice:
                minPrice = item
            if maxpro < item - minPrice:
                maxpro = item - minPrice
        return maxpro

주: 언제 한 문 제 를 '동적 기획' 의 방법 으로 풀 수 있 는 지 판단 할 수 있 습 니까?
    만약 에 만새기 한 문제 의 가장 좋 은 해결 (보통 최대 치 또는 최소 치) 이 고 문 제 는 몇 가지 문제 로 분해 할 수 있 으 며 서브 문제 사이 에 더 작은 서브 문제 가 중첩 되 어 있 으 면 동태 적 으로 계획 하 는 방법 으로 이 문 제 를 해결 하 는 것 을 고려 할 수 있다.
    동적 계획 으로 문 제 를 해결 하 는 몇 가지 특징:
1. 문제 의 최 적 화 를 구한다.
2. 전체 문제 의 가장 좋 은 해 는 각 키 문제 에 의존 하 는 가장 좋 은 해 이다.
3. 큰 문 제 를 몇 개의 작은 문제 로 분해 하 는데 이런 작은 문제 들 사이 에는 서로 겹 치 는 더 작은 문제 도 있다.
4. 위 에서 아래로 문 제 를 분석 하고 아래 에서 위로 문 제 를 풀다.