LeetCode Top Interview 150 - 121. Best Time to Buy and Sell Stock

처음 for문을 중첩으로 작성해주면 시간제한에 걸려서 통과를 못해줬다(시간복잡도를 생각 하지 않았다는...).

그래서 반복문 한번만 작성해주면서 처음 작성한 코드를 조금 바꿔 주면서 최대 이익을 찾는 로직을 찾아 주었다.

최대 이익을 찾으려면 제일 작은 수일때 구매해야하고

제일 큰수일 때 판매해야한다. 

//for문안에서 돌면서 max값찾기 ->O(N^2) (test만 되고 submit하면 시간제한에 걸린다)
// var maxProfit = function(prices) {

//     let maxProfit = 0
    
//     for(let i=0;i<prices.length;i++){
//         for(let j=i;j<prices.length;j++){
//             if(maxProfit < prices[j]-prices[i]){
//                 maxProfit = prices[j]-prices[i]
//             }
//         }
//     }
    
//     return maxProfit
// };

//작은수를 저장하고 손익 계산을 했을때 크면 저장
var maxProfit = function(prices) {

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

 

 

https://leetcode.com/problems/best-time-to-buy-and-sell-stock/?envType=study-plan-v2&envId=top-interview-150