[leetcode][122] Best Time to Buy and Sell Stock II

문제 : https://leetcode.com/problems/best-time-to-buy-and-sell-stock-ii/

---

주식 가격 배열이 주어진다.

어떤 주식을 샀을 때 해당 주식을 팔기 전까지는 주식을 구입할 수 없다고 하자.

주식을 사고 판다고 했을 때 얻을 수 있는 최대 이익은 얼마인가?

---

투 포인터로 해결했다.

 

처음에는 DP로 했었는데 이건 그렇게하면 TLE 난다.

다시 생각해보니 주식을 사고 나서 최대가를 찍었을 때 파는 거다.

 

주식가격이 상승 곡선이 시작하기 전 가장 최소값을 찍었을 때, 주식을 구입한다.

상승 곡선이 끝날 때, 주식의 가격이 최대가 됐을 때 주식을 판다.

주식을 판 다음 날부터 다시 위 과정을 반복한다.

 

이를 배열 끝날때까지 반복한다.

상승 곡선이 끝나기 전에 배열이 종료가 된다면(배열 종료시점까지 상승 곡선이 유지된다면) 가장 마지막 날 주식을 파는 것도 잊지말자.

 

시간복잡도는 O(N).

---

소스코드 : https://github.com/fpdjsns/Algorithm/blob/master/leetcode/easy/122.%20Best%20Time%20to%20Buy%20and%20Sell%20Stock%20II.cpp