[파이썬 알고리즘 인터뷰] 11. 주식을 사고팔기 가장 좋을 때

https://github.com/onlybooks/algorithm-interview

GitHub - onlybooks/algorithm-interview: <파이썬 알고리즘 인터뷰> 95가지 알고리즘 문제 풀이로 완성하는

1. 문제
leetcode 121. Best time to buy and sell stock
prices[i]가 i번째 날의 주식 가격인 배열 prices가 있다. 수익을 최대화시킬 수 있는 두 날짜를 골라 최대 수익을 리턴하여라. 만약 수익을 낼 수 없다면 0을 리턴하라.

2. 내 풀이

최대 이익, 최솟값을 관리하며 전체 배열을 탐색하는 방법으로 문제를 풀었다. 주어진 배열의 모든 원소에 대해 탐색을 진행한다. 탐색에서는 해당 원소가 현재까지의 최솟값보다 작다면 최솟값을 업데이트한다. 그리고 해당 원소에서 최솟값을 빼서 이익을 구하고, 그 값이 최대 이익보다 크다면 최대 이익을 업데이트 한다. 탐색이 끝나면 최대 이익을 리턴한다.