【LeetCode】121. Best Time to Buy and Sell Stock 해제

질문으로 연결

문제 개요

prices[i]는 i일째 가격을 나타내는 배열prices을 제공했다.
이때 주식을 사는 날과 파는 날을 각각 하루씩 골라 이윤을 극대화한다.
반환치는 거래 소득의 최대 이익이지만 이윤이 없는 상황에서도 갚는다0.
예:
이튿날 사고 다섯째 날에 팔다
prices[4] - prices[1] = 6 - 1 = 5
이익을 얻다.

구속

1\leq prices.length\leq 10^5

0\leq prices[i]\leq 10^4

생각

문제를 길이 1의 배열~길이 n의 배열 문제로 천천히 확장하면 최종 해결 방안을 얻을 수 있다.
그 질문은 다음과 같다.
n=1:
하루밖에 없기 때문에 매매 이윤도 제로다.
n=2:
첫날부터 이튿날까지 0으로 떨어졌다.
n=3:
과거 최저 가격의 다음날 사고 셋째 날에 팔면 최대 이윤은 4이다.
n=4:
과거에 가격이 가장 낮았던 다음날 사다.
4일차 가격이 새로 추가돼 3일차 판매이익이 더 컸다.
n=5:
과거에 가격이 가장 낮았던 다음날 사다.
5일차 가격이 새로 추가돼 3일차 판매가 5일차 판매보다 이익이 컸다.
n=6:
과거에 가격이 가장 낮았던 다음날 사다.
6일째 가격이 새로 추가되어 5일째 팔리는 이윤이 더 크다.
그래서 3가 답이 되었다.
위에서 말한 바와 같이,

지금까지 가장 큰 이윤: 6

지금까지의 최저 가격: 4

5, 앞에서부터 순서대로 보면,
res = max(res, prices[i]-min\_price)
답을 구하는 것으로 볼 수 있다.
지금까지 구현을 고려한 코드는 다음과 같습니다.

Input: prices = [7,1,5,3,6,4]
Output: 5