Best Time to Buy and Sell Stock

Best Time to Buy and Sell Stock

Explore - LeetCode

- 문제 내용 : 주어진 기간동안 단 한번의 구매와 판매가 가능하다. 최대의 이익값을 구해라

- 접근 방법

가장 낮은 값과 가장 높은 값을 찾아서 그 차를 구하면 된다.

단, 가장 낮은 값은 반듯이 가장 높은 값의 왼쪽에 있어야 한다.

 

• Prefix Sum을 사용한 접근

Prefix Sum을 1회 처리하게 되면 현재의 값이 이전 값 대비 높은곳에 위치 하는지 낮은 곳에 위치 하는지 알수 있다.

이를 통해서

현재의 index의 Prefix sum이 양수이고 이전 index Prefix Sum이 음수이면, min값을 업데이트하고 

이전 index의 prefix sum이 양수이고 현재 prefix sum이 음수이면, 이전 index Prefix sum을 중심으로 min, max 계산을 처리 하면 된다.

var maxProfit = function(prices) {
    let prefixSum = new Array(prices.length);
    prefixSum[0] = 0;

    let stock = 0;
    let result = 0;
    for (let i = 1; i < prices.length; i++) {
        prefixSum[i] = prices[i] - prices[i - 1];
    }

    let min = Infinity;
    let max = 0;

    for (let i = 0; i < prefixSum.length; i++) {
        if(prefixSum[i] <= 0 && prices[i] < min){
            result = Math.max(result, max - min);
            max = 0;
            min = prices[i];
        } else {
            max = Math.max(max,prices[i]);
        }
    }

    return min != Infinity ? Math.max(result, max - min) : 0;
};

그런데 막상 만들고 보니 참 의미 없는 짓이었다.

• min값만 유지 하는 방법

prices를 0에서 부터 min값을 찾아서 min값을 업데이트 시키고, 이후에 오는 모든 값에서 max의 차 값을 찾으면 된다.

그러면 min값은 반듯이 max의 왼쪽에 존재 하게 됨으로 문제가 없다.

var maxProfit = function(prices) {
    let minPrice = prices[0];
    let minResult = 0;

    for (let i = 0; i < prices.length; i++) {
        if (prices[i] < minPrice) {
            minPrice = prices[i];
        }
        minResult = Math.max(minResult, prices[i] - minPrice);
    }
    return minResult;
};