[LeetCode] 121 - Best Time to Buy and Sell Stock

문제

• 링크: https://leetcode.com/problems/best-time-to-buy-and-sell-stock
• 난이도: Easy
• 태그: 배열, 다이내믹 프로그래밍
• 결과: Time: 0 ms (100.00%), Space: 97.30 MB (86.54%)

풀이

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int res = 0;
        int minPrice = prices[0];
        int len = prices.size();
        for (int i = 0; i < len; ++i)
        {
            res = max(res, prices[i] - minPrice);
            minPrice = min(minPrice, prices[i]);
        }

        return res;
    }
};

범위를 늘려나가면서 수익을 최대화하면 된다. 오늘 수익을 최대화하려면, 이전까지의 날 중에서 가장 쌌던 날에 사고, 오늘 팔면 된다. 이렇게 계산한 값을 최댓값으로 업데이트 해나가면 된다.

배운 점과 후기

난이도가 Easy인데 그 정도로 느껴지진 않았다. 확실히 DP가 내 약점인 것 같다.

이 포스트는 달레 스터디(5주차)에서 진행한 Blind 75 문제집 풀이의 일부입니다.