[5. 배열] 5.6 주식 한 번 사고팔기

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

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

---

 

---

Q 5.6 주식 한 번 사고팔기

어떤 회사의 일일 주식 가격이 배열로 주어졌을 때 한 주를 한번 사고팔아서 남길 수 있는 최대 이익을 구하는 프로그램을 구해 보자.

---

간단한 방법은 최고가를 먼저 구한 뒤 그 최고가로부터 배열을 모두 빼 가장 큰 값을 구하는것이다.
하지만 이때 시간 복잡도는 O(n²)가 되므로, 이를 줄이기 위하여 분할 정복 알고리즘을 사용하려고 한다.
분할 정복 알고리즘은 부분배열을 구해 두개로 나누고, 각 부분에서 최대 이익을 구한후 둘중 최고가를 선택해 병합하는 방법이다.
ex) <310, 315, 275, 295, 260, 270, 290, 230, 255, 250> 에 대하여 다음과 같이 쓸수 있다.
<310, 315, 275, 295, 260, 270, 290, 230, 255, 250>
<310, 310, 275, 275, 260, 260, 260, 230, 230, 230>
----------------------------------------------------------------------
<    0,    5,      0,   20,     0,   10,   30,     0,   25,   20 > 으로 최대 이윤이 30이다.

다음은 소스코드와 결과이다.

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

결과