[LeetCode] 123. Best Time to Buy and Sell Stock III

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

Best Time to Buy and Sell Stock III - LeetCode

Best Time to Buy and Sell Stock III

 

주식 사고팔기 세번째 시리즈이다.

첫번째/두번째 시리즈를 먼저 풀고 푸는걸 권한다.

번외 시리즈는 이 시리즈를 다 풀고 풀는걸 권한다.

 

첫번째 시리즈

https://kohsmos.tistory.com/59

[LeetCode] 121. Best Time to Buy and Sell Stock

두번째 시리즈

https://kohsmos.tistory.com/60

[LeetCode] 122. Best Time to Buy and Sell Stock II

 

 

 

+ 번외 시리즈

https://kohsmos.tistory.com/56

[LeetCode] 309. Best Time to Buy and Sell Stock with Cooldown

 

 

오늘의 문제다.

주식을 사고 파는건 기존과 똑같은데, 이번엔 딱 두번만 사고 팔 수 있다.

두번째 시리즈와 크게 차이가 없다.

두번째 시리즈의 경우엔 stock_y와 stock_n이 하나로, 이를 계속 이용하는데,

이번 시리즈는 좀 여러개로 놔야한다.

 

stock_y[0] 은 첫번째 주식을 갖고 있는 상태

stock_y[1] 은 첫번째 주식을 팔고 두번째 주식을 갖고 있는 상태

 

stock_n[0], stock_n[1], stock_n[2] 는 각각

거래가 없는 상태, 첫 사고팔기만 완료된 상태, 두번째 사고팔기까지 완료된 상태이다.

이를 가지고 두번째 시리즈와 같이 식을 세우면 된다.

 

stock_y[0] = max(stock_y[0], stock_n[0] - price)

stock_y[1] = max(stock_y[1], stock_n[1] - price)

stock_n[1] = max(stock_n[1], stock_y[0]+price)

stock_n[2] = max(stock_n[2], stock_y[1]+price)

 

전체 코드는 아래와 같다.

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int stock_y[2]={INT_MIN,INT_MIN}, stock_n[3] = {0}, temp[2];
        for (int price:prices) {
            for (int i=0; i<2; i++) {
                temp[i] = stock_y[i];
                stock_y[i] = max(stock_y[i], stock_n[i]-price);
                stock_n[i+1] = max(stock_n[i+1], temp[i]+price);
            }
        }
        return max(stock_n[0],max(stock_n[1],stock_n[2]));
    }
};