LeetCode) best-time-to-buy-and-sell-stock

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

 

최초에는 단순하게 이중배열로 풀었는데

var maxProfit = function (prices) {
    let result = 0;
    for (let i = 0; i < prices.length - 1; i++) {
        for (let j = i + 1; j < prices.length; j++) {
            result = Math.max(prices[j] - prices[i], result);
        }
    }
    return result;
};

 

 

 

 

시간초과로 통과하지 못하였다.

Time Limit Exceeded :(

 

 

 

 

 

 o(n)으로 해결할 수 있는 방법을 고민하다가 다행히 아래와 같은 해결책이 떠올랐다.

var maxProfit = function (prices) {
    let max = 0;
    let min = prices[0]
    for (let i = 1; i < prices.length; i++) {
        min = Math.min(min, prices[i]);
        max = Math.max(max, prices[i] - min);
    }
    return max;
};

 

1. 최초에 0번째 값을 최소값으로 정한다.
2. 1번째부터 루프를 돌리는데, 최소값과 현재값을 비교하여 최소값을 정한다.
3. 최초 정해놓은 최대이익과 현재값을 이용하여 계산한 최대이익을 비교하여 큰 값을 할당한다.
4. 루프가 끝나면(o(n)) 최대 이익을 구할 수 있다.

 

직관적으로 다중루프를 도는 코드를 짜게 되는데, 조금 더 고민해보면 조금 더 나은 코드가 나오는 것 같다.