Подготовка к алгоритмическим задачам

Лучшее время для покупки и продажи акций: разбор задачи
Почему эта задача важна?
Задача о покупке и продаже акций позволяет оценить:
- 🧠 Умение находить оптимальные решения в последовательных данных
- ⚡ Способность оптимизировать алгоритмы с O(n²) до O(n)
- 📊 Навык анализа временных рядов
- 💰 Понимание базовых финансовых операций
Постановка задачи
Формулировка:
Дан целочисленный массив prices
, где prices[i]
— это цена NeetCoin в i-й день.
Вы можете выбрать один день для покупки одного NeetCoin и выбрать другой день в будущем для его продажи.
Верните максимальную прибыль, которую вы можете получить. Если вы решите не совершать никаких транзакций, прибыль будет равна 0.
Примеры:
// Первый пример ✅ Input: prices = [7, 1, 5, 3, 6, 4] Output: 5 Объяснение: Покупка во 2-й день (цена = 1) и продажа в 5-й день (цена = 6), прибыль = 6 - 1 = 5. // Второй пример ✅ Input: prices = [7, 6, 4, 3, 1] Output: 0 Объяснение: В этом случае лучше не совершать никаких транзакций, поскольку цены только падают.
Подходы к решению
Решение 1: Перебор всех пар (базовый подход)
function maxProfit(prices) { let maxProfit = 0 for (let i = 0; i < prices.length; i++) { for (let j = i + 1; j < prices.length; j++) { const profit = prices[j] - prices[i] maxProfit = Math.max(maxProfit, profit) } } return maxProfit }
Анализ решения:
✅ Очень простая реализация
✅ Легко понять логику
❌ Временная сложность O(n²)
❌ Неэффективно для больших массивов
Решай алгоритмические задачи как профи

Решение 2: Отслеживание минимальной цены 📉
function maxProfit(prices) { let minPrice = Infinity let maxProfit = 0 for (let i = 0; i < prices.length; i++) { if (prices[i] < minPrice) { minPrice = prices[i] } else { const profit = prices[i] - minPrice maxProfit = Math.max(maxProfit, profit) } } return maxProfit }
Характеристики:
✅ Оптимальная временная сложность O(n)
✅ Требует всего один проход по массиву
✅ Минимальное использование памяти O(1)
✅ Интуитивно понятная логика
Решение 3: Жадный алгоритм 🧮
function maxProfit(prices) { let maxProfit = 0 for (let i = 1; i < prices.length; i++) { // Если текущая цена выше вчерашней, можно получить прибыль if (prices[i] > prices[i - 1]) { const profit = prices[i] - prices[i - 1] maxProfit = Math.max(maxProfit, maxProfit + profit) } } return maxProfit }
Примечание: Это решение работает для задачи, когда разрешены множественные транзакции. Для текущей постановки задачи (только одна транзакция) оно не подходит.
Решение 4: Динамическое программирование 📚
function maxProfit(prices) { if (prices.length <= 1) return 0 const n = prices.length // dp[i][0] - максимальная прибыль на день i без акции в руках // dp[i][1] - максимальная прибыль на день i с акцией в руках const dp = Array(n) .fill() .map(() => Array(2).fill(0)) dp[0][0] = 0 // Нет акции в руках, прибыль 0 dp[0][1] = -prices[0] // Купили акцию, прибыль отрицательная for (let i = 1; i < n; i++) { dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i]) dp[i][1] = Math.max(dp[i - 1][1], -prices[i]) } return dp[n - 1][0] // Максимальная прибыль на последний день без акции }
Преимущества и недостатки:
✅ Можно расширить на более сложные случаи
✅ Систематический подход
❌ Избыточное использование памяти O(n)
❌ Сложнее для понимания
Решение 5: Оптимизированное динамическое программирование 🚀
function maxProfit(prices) { if (prices.length <= 1) return 0 let maxCashWithoutStock = 0 // Максимальная прибыль без акции let maxCashWithStock = -prices[0] // Максимальная прибыль с акцией for (let i = 1; i < prices.length; i++) { maxCashWithoutStock = Math.max( maxCashWithoutStock, maxCashWithStock + prices[i] ) maxCashWithStock = Math.max(maxCashWithStock, -prices[i]) } return maxCashWithoutStock }
Особенности:
✅ Оптимальная временная сложность O(n)
✅ Оптимальное использование памяти O(1)
✅ Сохраняет логику ДП без избыточности
❌ Менее наглядная реализация
Рекомендации по решению 💡
-
Выбор метода решения:
- 🚀 Отслеживание минимальной цены - самый интуитивный и эффективный подход
- 📊 ДП полезно для более сложных случаев (множественные транзакции)
- 🐌 Избегайте перебора для больших массивов
-
Важные моменты:
- 📝 Проверка пустого или одноэлементного массива
- 📉 Учет случаев, когда лучше не совершать сделок
- ⏱️ Важно учитывать временные ограничения (покупка должна быть раньше продажи)
Распространённые ошибки
- 🤦♂️ Забывание проверить, что продажа происходит после покупки
- 😅 Неправильная обработка случая постоянно падающих цен
- 🐛 Ошибки при инициализации переменных (например, минимальная цена)
Оптимизации
Ранний выход при определенных паттернах
function maxProfit(prices) { // Быстрая проверка тривиальных случаев if (prices.length <= 1) return 0 // Проверяем, постоянно ли растут цены let alwaysIncreasing = true for (let i = 1; i < prices.length; i++) { if (prices[i] <= prices[i - 1]) { alwaysIncreasing = false break } } if (alwaysIncreasing) { return prices[prices.length - 1] - prices[0] } // Основное решение let minPrice = prices[0] let maxProfit = 0 for (let i = 1; i < prices.length; i++) { if (prices[i] < minPrice) { minPrice = prices[i] } else { maxProfit = Math.max(maxProfit, prices[i] - minPrice) } } return maxProfit }
Оптимизация для особых паттернов цен
function maxProfit(prices) { if (prices.length <= 1) return 0 // Проверяем, постоянно ли падают цены let alwaysDecreasing = true for (let i = 1; i < prices.length; i++) { if (prices[i] > prices[i - 1]) { alwaysDecreasing = false break } } if (alwaysDecreasing) return 0 // Нет смысла проводить транзакции // Стандартное решение let minPrice = prices[0] let maxProfit = 0 for (let i = 1; i < prices.length; i++) { minPrice = Math.min(minPrice, prices[i]) maxProfit = Math.max(maxProfit, prices[i] - minPrice) } return maxProfit }
Заключение
При решении задачи важно помнить:
- 🤹♂️ Существует несколько подходов с разным балансом простоты и эффективности
- 📊 Самое элегантное решение обычно самое простое (отслеживание минимальной цены)
- 🧠 Понимание того, что мы хотим купить по минимальной цене и продать по максимальной
Эта задача демонстрирует, как можно оптимизировать алгоритм от квадратичной до линейной сложности, и является классическим примером применения однопроходных алгоритмов и жадного подхода. 🌟