SprintCode.pro

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

Super

Лучшее время для покупки и продажи акций: разбор задачи

9 мин чтения
алгоритмы
массивы
динамическое программирование

Почему эта задача важна?

Задача о покупке и продаже акций позволяет оценить:

  • 🧠 Умение находить оптимальные решения в последовательных данных
  • ⚡ Способность оптимизировать алгоритмы с 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²)

❌ Неэффективно для больших массивов

Пройди собеседование в топ-компанию
Платформа для подготовки

Решай алгоритмические задачи как профи

✓ Популярные алгоритмы✓ Разбор решений✓ AI помощь
Начать сейчас
Программист за работой

Решение 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)

✅ Сохраняет логику ДП без избыточности

❌ Менее наглядная реализация

Рекомендации по решению 💡

  1. Выбор метода решения:

    • 🚀 Отслеживание минимальной цены - самый интуитивный и эффективный подход
    • 📊 ДП полезно для более сложных случаев (множественные транзакции)
    • 🐌 Избегайте перебора для больших массивов
  2. Важные моменты:

    • 📝 Проверка пустого или одноэлементного массива
    • 📉 Учет случаев, когда лучше не совершать сделок
    • ⏱️ Важно учитывать временные ограничения (покупка должна быть раньше продажи)

Распространённые ошибки

  1. 🤦‍♂️ Забывание проверить, что продажа происходит после покупки
  2. 😅 Неправильная обработка случая постоянно падающих цен
  3. 🐛 Ошибки при инициализации переменных (например, минимальная цена)

Оптимизации

Ранний выход при определенных паттернах

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 }

Заключение

При решении задачи важно помнить:

  • 🤹‍♂️ Существует несколько подходов с разным балансом простоты и эффективности
  • 📊 Самое элегантное решение обычно самое простое (отслеживание минимальной цены)
  • 🧠 Понимание того, что мы хотим купить по минимальной цене и продать по максимальной

Эта задача демонстрирует, как можно оптимизировать алгоритм от квадратичной до линейной сложности, и является классическим примером применения однопроходных алгоритмов и жадного подхода. 🌟