<Hard> Best Time to Buy and Sell Stock IV (LeetCode : C#)

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

📕 문제 설명

날짜 별 주식 가격에 대한 배열이 주어질 때 최대 이익 구하기 (구매와 판매는 최대 k번씩 가능함)

한 날짜에는 사기 또는 팔기 하나의 거래만 가능하며 팔기 위해서는 미리 산 주식이 있어야 한다.

• Input
  최대 거래 횟수 k (int), 날짜별 주식 가격 배열 (int[])

• Output
  최대 이익

예제

풀이

dp -> 거래 안하거나 하거나 중 최대 값을 가져오는 식으로 점화식이 만들어진다.
거래를 안하는 경우 이전 날의 profit을 가져오고, 거래를 하는 경우 이전 거래까지 중 구매와 판매 차이 가장 크게 나는 값에 현재 price를 더한다.

public class Solution {
    public int MaxProfit(int k, int[] prices) {
        if (prices == null || prices.Length < 2 || k <= 0) 
        {
            return 0;
        }
        if (k >= prices.Length / 2) 
        {
            int maxProfit = 0;
            for (int i = 1; i < prices.Length; i++) 
            {
                if (prices[i] > prices[i-1]) // 사고 팔고 반복하기 (팔때 더 비싸다면)
                {
                    maxProfit += prices[i] - prices[i-1];
                }
            }
            return maxProfit;
        }

        int[,] dp = new int[k+1, prices.Length]; // 거래 횟수 별 최대 값 
        for (int i = 1; i <= k; i++) 
        {
            int maxDiff = -prices[0]; // 파고 사는 것 차이 제일 크게 만드는 값 저장 위함
            for (int j = 1; j < prices.Length; j++) 
            {
                dp[i, j] = Math.Max(dp[i, j-1], maxDiff + prices[j]); // 거래 안하거나 거래 하거나 (이전날 profit, 현재 기준 최대 이익 낼 수 있는 값)
                maxDiff = Math.Max(maxDiff, dp[i-1, j] - prices[j]); // 이전 거래까지 중 가장 큰 차이 나는 값
            }
        }
        
        return dp[k, prices.Length-1];
    }
}

결과