В чате просили ещё задачек. Вот вам на выходные)))
Дан массив целых положительных чисел, представляющих цену акции в разные дни (каждый элемент массива представляет день). Также дано целое число k, которое представляет количество сделок, которые вам разрешено совершить. Одна сделка состоит из покупки акции в определённый день и продажи в более поздний день (ВНИМАНИЕ: 1 сделка = 2 транзакции: покупка и продажа).
Найдите максимальную прибыль, которую вы можете получить, покупая и продавая акции, используя максимум k сделок.
Обратите внимание, что в определённый момент вы можете держать только одну акцию. То есть вы не можете купить более одной акции, и не можете купить акцию, если она у вас уже есть. Кроме того, не обязательно использовать все k сделок. Также допустим, что бюджет на покупку не ограничен.
Например,
prices = [5, 11, 3, 50, 60, 90]
k = 2
Результат: 93
//Покупка: 5, продажа: 11 (+6); покупка: 3, продажа: 90 (+87)
prices = [12, 14, 17, 10, 14, 13, 12, 15]
k = 3
Результат: 12
prices = [100, 30, 15, 10, 8, 25, 80]
k = 3
Результат: 72
//Только одна сделка
Усложнённый вариант: Написать решение со сложностью O(n*k) по времени и O(n) по памяти.Как обычно, приглашаю всех предлагать варианты решения в чате.
Источник: https://www.algoexpert.io/