Best Time To Buy And Sell Stock

problem

주어진 int 배열에서 날(index)마다 물건의 가격이 주어질때,가장 싼 날에 사고 비싼날에 팔아 가장 큰 이윤을 구하는 문제입니다.

https://leetcode.com/problems/best-time-to-buy-and-sell-stock/

solution

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int s = prices[0];
        int ans = 0;
        
        for(int p : prices){
            s = min(s, p);
            ans = max(ans, p-s);
        }
        return ans;
    }
};

후기

전에 풀었던 연속된 배열의 최대합을 구하는 문제와 유사점을 알 수 있어서 빠르게 풀 수 있었습니다.

이 문제에서의 핵심은
[1] -> 최대이윤 0 , 최소값 1
과
[1,2] -> 최대이윤 1, 최소값 1
[1,3] -> 최대이윤 2, 최소값 1
를 비교해보면 쉽게 알 수 있습니다.

[1,3,2] 가 있을 때

[1,3,2,x] 는 [1,3,2]의 답을 이용하면 쉽게 구할 수 있습니다.

x > 3 -> 최댓값: x-1(기존의 최솟값)
x <= 3 -> 최댓값: 2 (기존의 최댓값)

배열의 원소가 추가될 때, 추가되기 전의 답에서 간단한 계산으로 알 수 있기 때문입니다.

즉) 배열을 for문을 돌면서 값이 추가될때, 최소값을 갱신하고, 최대이윤도 갱신된다는 것입니다.