[5. 배열] 5.7 주식 두 번 사고팔기

[해당 문제는 266가지 문제로 정복하는 코딩 인터뷰]
책의 내용의 문제와 풀이를 베이스로 공부하는 내용이다. 

문제를 풀기전에 단순하게 문제를 푸는것이 목적이 아닌
시간복잡도와 공간복잡도의 관계를 계산하며,
자료구조의 이해도와 실력을 향상하는데 목적이 있다.

---

---

Q 5.7 주식 두 번 사고팔기

주식 한 주를 최대 두번까지 매매할 수 있을 때, 최대 이윤을 구하는 프로그램을 작성하라.
단, 두 번째 주식은 첫 번째 주식을 판 뒤에 구입할 수 있다.

---

간단한 방법은 매수-매도-매수-매도를 모든 경우를 조합하는 경우이다. 이때 시간복잡도는 O(n⁴)이다.
이를 줄이기 위하여 앞에서 부터 주식을 해당 날짜에 팔았을 경우의 최대 이익 값을 구하고,
뒤에서 부터 주식을 해당 날짜에 팔았을 경우의 최대 이익도 구한뒤 두 값을 더해 최대 이익을 구하는 방법을 이용하자.

ex) <12,11,13,9,12,8,14,13,15> 의 배열에서 앞에서 부터 최대 이익은 <0,0,2,2,3,3,6,6,7> 이다.
뒤에서 부터 최대 이익은 <7,7,7,7,7,7,2,2,0> 이다.
이 둘을 합치면
  0<0,0,2,2,3,3,6,6,7>     <= F[i-1]
<7,7,7,7,7,7,2,2,0>        <= B[i]
------------------------
<7,7,7,9,9,10,5,8,6>      이다. (두 번째 주식 구매는 첫 번째 주식 매도 이후에 발생해야 하므로 F[i-1] = 0 이 된다.)

해당 과정의 소스코드와 결과는 다음과 같다.

시간복잡도 O(n), 공간복잡도 O(n)

결과