[LeetCode] 188. Best Time to Buy and Sell Stock IV

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

Best Time to Buy and Sell Stock IV - LeetCode

Best Time to Buy and Sell Stock IV

 

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

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

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

 

첫번째 시리즈

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/61

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

 

 

 

 

+ 번외 시리즈

https://kohsmos.tistory.com/56

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

 

 

 

세번째 시리즈에서 최대 거래 수가 두번이 아닌 k번으로 확장된 경우이다.

앞서 세번째 시리즈의 코드를 애초에 for 문으로 2번 돌아가게 했으니 이를 k번으로만 바꾸면 된다.

k=0일때만 주의해주자.

 

전체 풀이 코드

 

class Solution {
public:
    int maxProfit(int k, vector<int>& prices) {
        if (k==0) return 0;
        int stock_y[k], stock_n[k+1], temp[k], M=0;
        for (int i=0; i<k; i++) {
            stock_y[i] = INT_MIN;
            stock_n[i] = 0;
        }
        stock_n[k] = 0;
        for (int price:prices) {
            for (int i=0; i<k; 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);
            }
        }
        for (int i=0; i<=k; i++) M = max(M, stock_n[i]);
        return M;
    }
};