Выбор ответа Junior Жадные обновлено
Акции: много сделок
Вопрос
Можно покупать и продавать акцию сколько угодно раз (держать одну). Как найти максимальную прибыль?
Попробуйте сами
Выберите вариант, и откроется разбор.
Показать ответ и разбор
Коротко
Правильный ответ: Сложить все положительные p[i] - p[i - 1]. Любой рост можно разбить на дневные приросты; собрав все положительные, получаем прибыль от всех подъёмов.
Варианты ответа
- Найти глобальный минимум и максимум и взять разность
- Динамика O(n²) по всем парам дней покупки и продажи
- Отсортировать цены и сложить разности соседних
- Сложить все положительные
p[i] - p[i - 1]правильный ответ
Разбор
Любой рост можно разбить на дневные приросты; собрав все положительные, получаем прибыль от всех подъёмов. O(n).
- Минимум и максимум подходят для одной сделки и только если минимум раньше максимума.
- Динамика излишне медленна.
- Сортировка теряет порядок дней.
Ответьте сами, а не прочитайте
В тренажёре вопрос попадёт в повторения и вернётся, когда начнёт забываться. Плюс билеты с зачётом: 20 вопросов, не больше 2 ошибок.