Blind 75 | Best Time to Buy and Sell Stock (Sliding Window 1 / 4)

https://leetcode.com/problems/best-time-to-buy-and-sell-stock/

Best Time to Buy and Sell Stock - LeetCode

 

Best Time to Buy and Sell Stock - 주식을 사고파는 최고의 시간

 

You are given an array prices where prices[i] is the price of a given stock on the ith day.

You want to maximize your profit by choosing a single day to buy one stock and choosing a different day in the future to sell that stock.

Return the maximum profit you can achieve from this transaction. If you cannot achieve any profit, return 0.

 

prices[i]가 i째 날의 주식의 가격인 prices 배열이 주어진다.

한 날을 선택하여 주식을 사고 다른 날에 팔아 최대 이익을 얻고 싶을 때, 그 값이 얼마인지 구하라. 어떠한 이득도 얻을 수 없을 땐 0을 리턴하라.

 

 

 

풀이

 

단순하게 푸는 방법도 있지만 슬라이딩 윈도우 기법을 사용해서 풀어본다.

 

left, right을 각 0, 1에 두고 이익을 얻을 수 있다면 계산한 후 그전에 계산된 max 값과 비교한다.

 

그리고 right을 이동시키는데 만약 이득을 얻을 수 없다면 left를 right으로 이동시킨다.

 

 

코드

 

 

슬라이딩 윈도우 기법에서는 right과 left를 어느 조건에서 움직여야 하는지가 제일 중요하다.