(Easy - Greedy) Leetcode - 121. Best Time to Buy and Sell Stock

이 문제는 날짜 별로 주식의 가격이 적힌 배열이 주어집니다.

그러면 어떤 날에 주식을 산 후 다른 날에 주식을 팔 때 가장 큰 이익이 얼마인지 찾는 문제입니다.

 

간단하게 하루하루가 지날 때마 가장 가격이 낮을 때를 사는 날로 정하고 가장 낮은 가격을 갱신해줍니다.

이때 갱신한 날이 주식을 산 날입니다.

이루 하루가 지날때마다 가장 낮은 가격을 빼 이득을 계산하며 최대 이득을 갱신해줍니다.

 

    int maxProfit(vector<int>& prices) {
        int profit = 0;
        int minPrice = prices[0]; // 첫날은 팔 수 없습니다.
        for (int i = 1; i < prices.size(); ++i) { // 2일째부터 판매가 가능하니 index 1부터 시작
            if (prices[i] < minPrice) // 가장 가격이 낮을 때 주식을 구매
                minPrice = prices[i];
            else
            	// 가장 낮은 가격에 산다고 가정하고 매일 주식을 팔았을 때 이득을 갱신
                profit = std::max(profit, prices[i] - minPrice); 
        }
        return profit;
    }