Best Time to Buy and Sell Stock

풀이

쉽게 보면 그리디 문제임

근데 대충 그리디 알고리즘 짜면 개망함

2중포문? 개망함ㅇㅇ

이게 제약조건인데 최대 리스트의 길이가 $10^5$임
2중포문돌면 10억회, 약 10초임

우린 이걸 $O(N^2)$이 아닌 $O(N)$으로 끝낼 방향을 찾아야함

먼저 문제의 핵심은 다음과 같음

1. 무조건 파는 날짜보다 사는 날짜가 빠르다
2. 파는 날의 가격 - 사는 날의 가격 중에 가장 큰 것을 고르면 된다

즉, 사는 날의 가격중 가장 싼 날을 찾고, 파는 날의 가격중 가장 비싼 날을 찾으면 됨

그리고 사는 날은 무조건 파는 날보다 빠름

정리해보면 다음과 같음

1. 사는 날은 가장 저렴한 날이기만 하면 되므로, 저렴한 날이 나올때 마다 갱신
2. 파는 날은 사는 날과 관계없이 팔기만 하면 되므로, 파는날 - 사는날 가격에서 가장 큰 값만 고르기

이걸 코드로 구현하면 다음과 같음

class Solution {
public:
    int maxProfit(vector<int>& prices) {

        int minP = prices[0];
        int max = 0;

        for(int p : prices)
        {
            minp = std::min(minP, p);
            max = std::max(max, p - minP);
        }

        return max;
    }
};

어? 싶지?

minP가 사는 날 중 가장 저렴한 값임

그리고 사는 날과 관계없이 파는날 가격에서 가장 싼 값을 뺀 가격중 가장 큰 값을 고르면 됨

만약 [7,1,3]이 있다고 가정해보면

1. i = 0, minP는 7, max = max(max(0), prices[i] - minP(0))
2. i = 1, minP는 1, max = max(max(0), prices[i] - minP(0))
3. i = 2, minP는 1, max = max(max(0), prices[i] - minP(2))

이렇게 minP가 갱신이 되면 max는 무조건 0이 되어,
항상 최대값만을 갱신하는 코드가 완성되는거임