[Leet] - 121. Best Time to Buy and Sell Stock [dp] - c++

mopevxw·2022년 2월 3일
0

LeetCode

목록 보기
13/21

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

dp풀이


1.int v[i] = i일 까지 최대 profit 저장 배열
2.index= 0(시작) 지점에서는 buy배열에 값 저장
3.prices배열 마지막날까지 이동하면서 바로 전날 까지의 최대 이익v[i-1]과 현재 가격에 팔았을 때 profit 비교
4.buy 가격 비교 후 최신화

public:
    int maxProfit(vector<int>& prices) {
        vector<int> v(100000);
        v[0]=0;
        int profit;
        int buy=prices[0];
        int sell=prices[0];
        
        for(int i=1;i<prices.size();i++){
            sell=prices[i];
            v[i]=max(sell-buy,v[i-1]);
            
            if(buy>prices[i]) buy = prices[i];
            
            
            
        }
        return v[prices.size()-1];
    }
};

0개의 댓글