python에서 최대 2번 주식을 사고팔고 최대 수익을 구하는 프로그램

<시간/>

가격이라고 하는 숫자 목록이 있고 시간순으로 회사의 주가를 나타내는 목록이 있다고 가정하면 해당 주식을 최대 2번 사고팔 때 얻을 수 있는 최대 이익을 찾아야 합니다. 먼저 사서 팔아야 합니다.

따라서 입력이 가격 =[2, 6, 3, 4, 2, 9]와 같으면 출력은 11이 됩니다. 가격 2에서 구매한 다음 6에서 판매하고 다시 2에서 구매하고 판매할 수 있기 때문입니다. 9시에.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

first_buy :=-inf, first_sell :=-inf
second_buy :=-inf, second_sell :=-inf
가격의 각 px에 대해 다음을 수행합니다.
- first_buy :=first_buy 및 -px의 최대값
- first_sell :=first_sell 및 (first_buy + px)의 최대값
- second_buy :=second_buy 및 (first_sell - px)의 최대값
- second_sell :=second_sell 및 (second_buy + px)의 최대값
최대 0, first_sell 및 second_sell을 반환

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

예시

class Solution:
   def solve(self, prices):
      first_buy = first_sell = float("-inf")
      second_buy = second_sell = float("-inf")
      for px in prices:
         first_buy = max(first_buy, -px)
         first_sell = max(first_sell, first_buy + px)
         second_buy = max(second_buy, first_sell - px)
         second_sell = max(second_sell, second_buy + px)
      return max(0, first_sell, second_sell)

ob = Solution()
prices = [2, 6, 3, 4, 2, 9]
print(ob.solve(prices))

입력

[2, 6, 3, 4, 2, 9]