[LeetCode] 0123. 주식을 사고팔기에 가장 좋은 시기 III

Python, C++, JavaScript, SQL 및 TypeScript의 다양한 LeetCode 솔루션을 살펴보세요. 여러 프로그래밍 언어로 인터뷰 준비, 학습 및 코드 연습에 적합합니다. Github 레포 링크

딱딱한

배열이 주어졌습니다. 물가 어디 가격[i] 은 주어진 주식의 가격이다. 나는 ^일 낮.

달성할 수 있는 최대 이익을 찾아보세요. 최대 2개의 거래.

메모: 동시에 여러 거래에 참여할 수 없습니다(즉, 주식을 다시 구매하기 전에 반드시 해당 주식을 판매해야 합니다).

예시 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입니다.

제약:

1 <= 가격.길이 <= 10 ⁵
0 <= 가격[i] <= 10 ⁵

파이썬

				
					# 시간 복잡도: O(n) # 공간 복잡도: O(n) fromtyping import List class Solution(object): def maxProfit(self, 가격: List[int]) -> int: if len(prices) <= 1 : 0 반환 leftMin = 가격[0] rightMax = 가격[-1] length = len(price) leftProfits = [0] * 길이 rightProfits = [0] * (length + 1) for l in range(1, length): leftProfits[l] = max(leftProfits[l - 1], 가격[l] - leftMin) leftMin = min(leftMin, 가격[l]) r = 길이 - 1 - l rightProfits[r] = max(rightProfits[r + 1], rightMax - 가격[r]) rightMax = max(rightMax, 가격[r]) maxProfit = 0 print(leftProfits) print(rightProfits) for i in range(0, length): maxProfit = max(maxProfit, leftProfits[ i] + rightProfits[i + 1]) maxProfit 가격 = [7, 1, 5, 3, 6, 4]를 반환합니다. # leftProfit = [0, 0, 4, 4, 5, 5] # rightProfit = [5, 5 , 3, 3, 0, 0, 0] print(Solution().maxProfit(price))

딱딱한

파이썬

관련 기사