Сложность: hard
Вам дан массив цен, где prices[i] — это цена данной акции в i-й день.
Найдите максимальную прибыль, которую вы можете получить. Вы можете совершить не более двух транзакций.
Обратите внимание: вы не можете участвовать в нескольких транзакциях одновременно (то есть, вы должны продать акцию, прежде чем снова её купить).
Пример:
Input: prices = [3,3,5,0,0,3,1,4]
Output: 6
Explanation: Buy on day 4 (price = 0) and sell on day 6 (price = 3), profit = 3-0 = 3.
Then buy on day 7 (price = 1) and sell on day 8 (price = 4), profit = 4-1
👨💻 Алгоритм:
1️⃣Наивная реализация этой идеи заключалась бы в разделении последовательностей на две части и последующем перечислении каждой из подпоследовательностей, хотя это определенно не самое оптимизированное решение.
Для последовательности длиной N у нас было бы N возможных разделений (включая отсутствие разделения), каждый элемент был бы посещен один раз в каждом разделении. В результате общая временная сложность этой наивной реализации составила бы O(N²).
2️⃣Мы могли бы сделать лучше, чем наивная реализация O(N²). Что касается алгоритмов разделяй и властвуй,
одна из общих техник, которую мы можем применить для оптимизации временной сложности, называется динамическим программированием (DP), где мы меняем менее повторяющиеся вычисления на некоторое дополнительное пространство.
3️⃣Сначала мы обозначаем последовательность цен как Prices[i], с индексом начиная от 0 до N-1. Затем мы определяем два массива, а именно left_profits[i] и right_profits[i].
Как следует из названия, каждый элемент в массиве left_profits[i] будет содержать максимальную прибыль, которую можно получить от выполнения одной транзакции в левой подпоследовательности цен от индекса ноль до i, (т.е. Prices[0], Prices[1], ... Prices[i]).
Например, для подпоследовательности [7, 1, 5] соответствующий left_profits[2] будет равен 4, что означает покупку по цене 1 и продажу по цене 5.
😎 Решение:
var maxProfit = function (prices) {
if (prices.length <= 1) return 0;
let left_min = prices[0];
let right_max = prices[prices.length - 1];
let length = prices.length;
let left_profits = new Array(length).fill(0);
let right_profits = new Array(length + 1).fill(0);
for (let l = 1; l < length; ++l) {
left_profits[l] = Math.max(left_profits[l - 1], prices[l] - left_min);
left_min = Math.min(left_min, prices[l]);
let r = length - 1 - l;
right_profits[r] = Math.max(
right_profits[r + 1],
right_max - prices[r],
);
right_max = Math.max(right_max, prices[r]);
}
let max_profit = 0;
for (let i = 0; i < length; ++i) {
max_profit = Math.max(
max_profit,
left_profits[i] + right_profits[i + 1],
);
}
return max_profit;
};Ставь 👍 и забирай 📚 Базу знаний