배열 A가 있다고 가정합니다. 여기서 A[i]는 i일에 주어진 주식의 가격을 나타냅니다. 우리는 최대의 이익을 찾아야 합니다. 우리는 최대 하나의 거래를 완료할 수 있습니다. (거래는 주식을 사고 파는 것을 의미합니다). 그러나 우리는 동시에 여러 거래에 참여할 수 없다는 점을 명심해야 합니다. 그래서 우리는 새 주식을 사기 전에 주식을 팔아야 합니다.
배열이 A =[7, 1, 5, 3, 6, 4]와 같다고 가정하면 결과는 5가 됩니다. 보시다시피 2일차(인덱스 1)에 구매하면 다음과 같이 1이 됩니다. 구매 가격. 그러면 5일차에 매도하면 이익은 6 – 1 =5가 됩니다.
이 문제를 해결하려면 다음 단계를 따르십시오 -
- A와 같은 크기의 leftMin, rightMax 2개의 배열을 만들고 0으로 채웁니다.
- leftMin[0] =A[0]
- 범위 1에서 A – 1의 길이까지 i의 경우, leftMin[i] =leftMin[i – 1] 및 A[i]의 최소값
- rightMax[n-1] =A[n – 1]
- A – 1에서 1까지의 범위 길이에 있는 i의 경우 rightMax[i] =rightMax[i + 1] 및 A[i]의 최대값
- 설정 답변:=0
- 범위 0에서 A – 1의 길이에 있는 i의 경우, answer :=최대 답변 및 rightMax[i + 1] – leftMin[i]
- 반환 응답
더 나은 이해를 위해 구현을 살펴보겠습니다.
예시
class Solution(object): def maxProfit(self, prices): """ :type prices: List[int] :rtype: int """ if not prices: return 0 leftMin,rightMax = [0 for i in range(len(prices))],[0 for i in range(len(prices))] leftMin[0] = prices[0] for i in range(1,len(prices)): leftMin[i] = min(leftMin[i-1],prices[i]) #print(leftMin) rightMax[-1]= prices[-1] for i in range(len(prices)-2,-1,-1): rightMax[i] = max(rightMax[i+1],prices[i]) #print(rightMax) ans = 0 for i in range(len(prices)-1): ans = max(ans,rightMax[i+1]-leftMin[i]) return ans ob1 = Solution() print(ob1.maxProfit([7,2,5,8,6,3,1,4,5,4,7]))
입력
prices = [7,2,5,8,6,3,1,4,5,4,7]
출력
6