LeetCode 121 - Best Time to Buy and Sell Stock (Easy)

문제

LeetCode - 121번

풀이 과정

시세가 주어진 배열에서 주식을 사고 팔았을 때 가장 큰 이윤을 남기는 방법을 찾는 문제입니다.

직관적으로 주식이 가장 낮을 때 사서 가장 높을 때 파는 것이 가장 큰 이윤을 남긴다는 것을 알 수 있습니다.
따라서 배열의 각 요소를 순회하며 최소 비용 값을 갱신해주는 것과 동시에 각 상품마다 현재 인덱스까지 탐색한
최소 비용 과의 차이값을 통해 최대 판매 수익 을 O(N)의 시간 복잡도로 얻을 수 있습니다.

정당성 증명

최소 비용을 선택하는 우리의 탐욕 알고리즘 은 자명하기 때문에 간단히 증명하고
O(N) 에 탐색을 수행할 수 있다는 정당성을 따져보겠습니다.

우선 매 시세마다 최소비용을 갱신한 결과 최적해를 찾지 못했다고 하겠습니다.
이 경우 실제 최적해(가정)에는 위 알고리즘이 처음 잘못 선택한 비용 J 보다 큰 시세 K가 있음에도 최적해를 찾았다는 뜻입니다.
여기서 K 대신에 J 를 선택할 경우 최대 이윤은 커지면 커졌지 절대 손해보는 일은 발생하지 않습니다.

그렇다면 O(N) 에 탐색을 수행하는 것이 올바른 최적해를 구하는 것을 어떻게 보장해줄 수 있을 까요?

이를 위해 한 시점 i 에서 price[i] - minValue 를 통해 최대 이윤을 계산했다고 가정하겠습니다.
이때 우리가 필요한 minValue 는 0 ~ i 까지의 최저 시세 인 것은 자명한 사실입니다.
우리의 알고리즘이 시점 i 까지 탐색을 수행하는 동안 계속 최저 시세를 계속 갱신하였으므로
올바른 답을 구할 수 있다는 것을 보장할 수 있습니다.

코드

/**
 * @param {number[]} prices
 * @return {number}
 */
var maxProfit = function (prices) {
  let minValue = 987654321;
  let maxProfit = 0;

  for (let price of prices) {
    minValue = Math.min(minValue, price);
    maxProfit = Math.max(maxProfit, price - minValue);
  }

  return maxProfit;
};