[75 LeetCode] 11 - Best Time to Buy and Sell Stock

[75 LeetCode]는 코딩테스트 연습을 위해 한 페이스북 개발자가 추천하는 75가지 알고리즘 문제를 풀어보는 시리즈이다.

블라인드 원문:
https://www.teamblind.com/post/New-Year-Gift---Curated-List-of-Top-75-LeetCode-Questions-to-Save-Your-Time-OaM1orEU

문제 링크: https://leetcode.com/problems/best-time-to-buy-and-sell-stock/

Best Time to Buy and Sell Stock - LeetCode

 

간단히 하면, 임의의 a, b (a < b)에 대해 max(prices[b] - prices[a])를 찾는 문제다.

뒤에서부터 순회하여,
1) prices[b]가 현재 최대값보다 큰 경우 현재 최대값을 prices[b]로 설정해준다.
2) 작거나 같은 경우 현재까지의 최대이득과, 현재 최대값 - prices[b]를 비교하여 최대이득을 수정해준다.

뒤에서부터 돌기 때문에 1)에서 현재 최대값을 바꿔줄 수 있다.
이후에 최대값보다 작은값이 나올 때 최대이득을 계산하는데,
바뀐 최대값과의 차이가 기존 최대값과의 차이보다 크기 때문.

 

var maxProfit = function(prices) {
    let ret = 0;
    let max = 0;

    for(let i = prices.length - 1; i >= 0; i--) {
        prices[i] <= max
            ? ret = Math.max(ret, max - prices[i])
            : max = prices[i]
    }
    return ret;
};