3방법 ②: 한 번 반복으로 최대 수익 찾기

 

모든 경우를 비교하는 방법인 프로그램 18-1은 간단하고 직관적이지만, 불필요한 비교를 너무 많이 합니다. 생각을 조금 바꿔 보면 훨씬 효율적인 방법을 떠올릴 수 있습니다.

프로그램 18-1이 사는 날을 중심으로 생각한 것이라면 이번에는 파는 날을 중심으로 생각을 바꿔보겠습니다. 예를 들어 6월 10일에 9,800원을 받고 주식을 팔았다고 가정해 봅시다. 이때 얻을 수 있는 최고 수익은 6월 10일 이전에 가장 주가가 낮았던 날인 6월 5일에 7,800원에 산 경우이므로 2,000원입니다. 만약 6월 11일에 10,200원에 팔았다면, 6월 5일 7,800원과의 차이인 2,400원이 최대 수익입니다. 즉, 파는 날을 기준으로 이전 날들의 주가 중 최솟값만 알면 최대 수익을 쉽게 계산할 수 있습니다. 이 아이디어를 조금 더 체계적으로 적어 보면 다음과 같습니다.

 

1 | 최대 수익을 저장하는 변수를 만들고 0을 저장합니다.

2 | 지금까지의 최저 주가를 저장하는 변수를 만들고 첫째 날의 주가를 기록합니다. 

3 | 둘째 날의 주가부터 마지막 날의 주가까지 반복합니다. 

4 | 반복하는 동안 그날의 주가에서 최저 주가를 뺀 값이 현재 최대 수익보다 크면 최대 수익 값을 그 값으로 고칩니다. 

5 | 그날의 주가가 최저 주가보다 낮으면 최저 주가 값을 그날의 주가로 고칩니다.

6 | 처리할 날이 남았으면 4번 과정으로 돌아가 반복하고, 다 마쳤으면 최대 수익에 저장된 값을 결괏값으로 돌려주고 종료합니다.