using System;

​

namespace MaxProfitKTransactions

{

  class Program

  {

    public static void Main()

    {

      int k = 2;

      int[] prices = { 5, 11, 3, 50, 60, 90 };

      Console.WriteLine($"Максимальная прибыль от {k} сделок: " + MaxProfit(prices, k));

​

      k = 3;

      prices = new int[] { 12, 14, 17, 10, 14, 13, 12, 15 };

      Console.WriteLine($"Максимальная прибыль от {k} сделок: " + MaxProfit(prices, k));

​

      k = 3;

      prices = new int[] { 100, 30, 15, 10, 8, 25, 80 };

      Console.WriteLine($"Максимальная прибыль от {k} сделок: " + MaxProfit(prices, k));

    }

​

    static int MaxProfit(int[] prices, int k)

    {

      var totalDays = prices.Length;

      if (totalDays == 0) return 0;

​

      int[] oddProfits = new int[totalDays];

      int[] evenProfits = new int[totalDays];

      int[] previousProfits, currentProfits;

​

      // проходим по сделкам от 1 до k (ряд для сделки 0 заполнен нулями при объявлении)

      for (int transaction = 1; transaction <= k; transaction++)

      {

        //используем только два ряда таблицы максимальных прибылей 

        if (transaction % 2 == 0)

        {

          previousProfits = oddProfits;

          currentProfits = evenProfits;

        }

        else

        {

          previousProfits = evenProfits;

          currentProfits = oddProfits;

        }

​

        int maxIncomeSoFar = int.MinValue;

        // считаем прибыли по дням (1й день прибыль 0)

        for (int day = 1; day < totalDays; day++)

        {

          // определяем максимальную выгоду от покупки с учётом предыдущих сделок

          maxIncomeSoFar = Math.Max(maxIncomeSoFar, previousProfits[day - 1] - prices[day - 1]);

​

          // считаем максимальную прибыль от текущей сделки в текущий день

          currentProfits[day] = Math.Max(currentProfits[day - 1], maxIncomeSoFar + prices[day]);

        }

      }

​

      // возвращаем последнее значение прибыли из соответствующего ряда прибылей

      return (k % 2 == 0) ? evenProfits[totalDays - 1] : oddProfits[totalDays - 1];

    }

  }

}

​