LeetCode : 122. Best Time to Buy and Sell Stock II

정말 Greedy에 약하다......ㅜ

정답 코드를 보면 아~~~맞네 이런 리액션이 나올 정도로 코드는 간결하고 간단하다.

 

간단하게, 발생할 수 있는 예시는 다음과 같다.

1. 지속적으로 증가하는 구간이 없고 올라갔다 내려갔다 들쑥날쑥한 그래프( [7, 1, 4, 3, 5, 2, 4] )

이 경우는, 위에 그림에서 표시한 A+B>C이다. 따라서, 지속적으로 증가하는 부분이 없는 경우에는 1->5로 바로 점프를 하는 것보다는

각각 1->4, 3->5로 주식을 사고 파는 것이 훨씬 이득이다.

 

2. 지속적으로 증가하는 구간이 있는 그래프( [1, 7, 2, 3, 5, 7, 2] )

 

위 그림에서는 A+B+C = D이다. 따라서, 지속적으로 증가하는 부분의 경우에는 2->7로 바로 점프를 하는 것이 2->3, 3->5, 5->7로 가는 것과 똑같은 수익을 낸다.

 

==> 결론적으로, 내려가는 구간에서는 주식을 사고 파는 행위를 하지 않고 올라가는 모든 각각의 구간에서 수익을 창출하면 된다. (특정 지점에서 특정 지점으로 몇 칸을 점프하는 것은 지속적으로 증가하는 구간에서는 최대 이익을 낼 수 있지만, 그렇지 않은 그래프에서는 최대 이익이 아니다.)

 

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        // 내려가는 구간은 절대 사지 않고
        // 올라가는 구간에서만 사고 판다.
        int ans = 0;
        for(int i=1; i<prices.size(); i++){
            if(prices[i]>prices[i-1]){
                ans += (prices[i]-prices[i-1]);
            }
        }
        
        return ans;
    }
};