리트코드 주식을사고파는가장좋은시기 c++ // 이분탐색(슬라이딩윈도)+그리디, dp

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

1. 이분탐색(슬라이딩윈도)+그리디

nC2완탐은 불가능함.

이분탐색? st=0, en=n-1? -> 자꾸 분기가 일어남 -> 슬라이딩 윈도우?

1.1. buy(st)=0, sell(en)=1로 시작하고

음수이면, 비싸게 사고, 싸게 판다는 뜻인데

가격이 싼날에 사면 된다.

양수면, 정답갱신후 추가 탐색한다.

1.2. 부분최적해가 전체최적해가 된다.(그리디)

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int ret=0;
        int sell=0,buy=0;
        int n=prices.size();
        if(n==1) return 0;
        for(int sell=1;sell<n;++sell){
            if(prices[sell]>prices[buy]){ //더비싸게 파는날이 있는지 탐색한다.
                ret=max(ret,prices[sell]-prices[buy]);
            }
            else{ //파는가격이 싸다는 말(sell<buy)이므로, 싼가격에 사면된다.
                buy=sell;
            }
        }
        return ret;
    }
};

 

2. dp 

2.1. 현재까지본것중 제일싼가격, 최대이익을 저장,갱신 하면서 문제를 진행한다. //배열, 변수에 저장함

2.2. 의사코드

여기에는 좋은 설명이 없고 코드만 있어서 코드를 제공하지 않고 어떻게 해결했는지 최선을 다해 설명하겠습니다. 나는 다른 가능한 해결책이 있다고 확신하지만 이것이 나에게 효과가 있었던 방식입니다.

여기서는 이중 for 루프의 무차별 방식이 필요하지 않으며 이 문제는 슬라이딩 윈도우 기술이 필요하기 때문에 동적 프로그래밍으로 표시됩니다 .

구매 후 판매해야 하며 이익을 극대화하려고 노력한다는 사실을 바탕으로 가격을 반복할 수 있으며 다음 두 가지만 고려하면 됩니다.
1.) 이 가격이 이전에 본 다른 어떤 가격보다 저렴합니까? ?
2.) 현재 가격에서 내가 찾은 가장 저렴한 가격을 빼면 지금까지 본 것보다 더 큰 수익이 나나요?

재미있는 점은 #1이 참이면 #2도 참일 수 없으므로 확인할 필요가 없다는 것입니다.

[4,1,5,2,7]의 예를 생각해 봅시다.

4는 시작하는 데 가장 저렴한 가격이고 첫날에는 판매할 수 없으므로 maxProfit은 0입니다.
1은 이제 우리가 본 것 중 가장 저렴한 가격입니다. 지금 판매하면 돈을 잃을 것이므로 maxProfit을 업데이트할 수 없습니다.
5는 1보다 저렴하지 않지만 지금 팔면 maxProfit은 4가 됩니다! 나중을 위해 저장해 두는 것이 좋습니다
2는 1보다 저렴하지 않으며 판매하면 1의 이익만 얻습니다. 여기서는 아무것도 할 필요가 없습니다.
7은 1보다 저렴하지는 않지만 여기서 판매하면 maxProfit을 6으로 증가시켜 반환할 수 있는 최고의 이익이 됩니다.

2.3. 전체코드

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        if (prices.empty()) return 0;

        int minPrice = prices[0]; //현재까지 본것중 제일 싼거
        int maxProfit = 0;

        for (int i = 1; i < prices.size(); ++i) {
            // Calculate the profit if we sell at prices[i]
            int profit = prices[i] - minPrice;

            // Update maxProfit if we can do better by selling at prices[i]
            maxProfit = max(maxProfit, profit);

            // Update minPrice to the minimum value seen so far
            minPrice = min(minPrice, prices[i]);
        }

        return maxProfit;
    }
};