[LeetCode] Best Time to Buy and Sell Stock II - Javascript

Best Time to Buy and Sell Stock II

[주식 거래를 할 수 있는 만큼 해서 가장 큰 이익을 보기]

제약 조건 

1 <= prices.length <= 3 * 10^4
0 <= prices[i] <= 10^4

Example

ex1) Input: prices = [7,1,5,3,6,4]
     Output: 7
     Explanation: Buy on day 2 (price = 1) and sell on day 3 (price = 5), profit = 5-1 = 4.
     Then buy on day 4 (price = 3) and sell on day 5 (price = 6), profit = 6-3 = 3.
     Total profit is 4 + 3 = 7.

ex2) Input: prices = [1,2,3,4,5]
     Output: 4
     Explanation: Buy on day 1 (price = 1) and sell on day 5 (price = 5), profit = 5-1 = 4.
     Total profit is 4.

ex) Input: prices = [7,6,4,3,1]
    Output: 0
    Explanation: There is no way to make a positive profit, so we never buy the stock to achieve the maximum profit of 0.

접근 방식

이전 문제에서 모든 경우의 수를 전부 탐색해 타임아웃에 걸려,
이전 문제의 특성을 곰곰이 생각해 다르게 생각해 풀었다.
단순히 생각해 가장 저렴하게 구매해 가장 비싸게 팔아야 하는 경우의 수를 모두 생각해야 할 것 같지만,
생각해 보면 그 차이는 하루마다 주식을 사고파는 차이와 같다.

 

아래 사진의 좌표를 보자

1일차에 주식을 1원에 구매해 5일차에 20원에 팔아 19원의 이득을 보는 것과
1일차에 주식을 2일차에 팔고 1원의 이익을 3일까지 총 3원의 이익을 보고
4일차의 주식을 5일차에 16원에 팔아 총 19원의 이득을 보는 것과 같다.

 

즉 저점에서 최고점까지의 거리는 모든 연속된 차이의 합과 같다.
결국 오늘의 주식 차액과 어제의 주식 차액이 이익이라면 무조건 판매하는 게 이득인 것이다.

전체코드

/**
 * @param {number[]} prices
 * @return {number}
 */
var maxProfit = function (prices) {
   let tmp = 0;
   let sum = 0;
   for (let i = 1; i < prices.length; i++) {
      tmp = prices[i] - prices[i - 1];
      if (tmp > 0) {
         sum = sum + tmp;
         tmp = 0;
      }
   }
   return sum;
};

 

다른 sovle 코드

다른 풀이를 봐도 내가 접근한 방법과 비슷하게 푼 것 같다.