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

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

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)

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

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

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

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

Оптимизации

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

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
}

Заключение

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

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

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

Попробуй решить популярные задачи

Массивы и Хеширование