Я столкнулся с указанной ниже проблемой - или с ее вариантом - в нескольких группах по изучению алгоритмов за последний год:
Напишите функцию, которая принимает массив цен акций и возвращает максимальную прибыль, которую вы могли получить от одной покупки и одной продажи. Цены в массиве указаны в той последовательности, в которой они были куплены, и могут быть проданы только после того, как они были куплены. Если получение прибыли невозможно, верните -1.
Эта проблема выделялась для меня среди десятков, над которыми я работал, потому что даже после ее решения - зная и помня, что решение оказалось менее сложным, чем я первоначально представлял, я все еще изо всех сил пытался найти эффективное решение.
Вопросы заказа
Я впервые столкнулся с этой проблемой, когда только узнал о объекте Math и всех его удобных встроенных методах. Я был рад их использовать! Я думал, что это прекрасная возможность для Math.min () и Math.max () моего пути к решению.
Покупай дешево, продавай дорого!
Но возникла проблема: если максимальное значение было найдено при более низком индексе, чем минимальное, вы обнаружили наибольшую разницу между значениями, но это не задача. Вы должны купить акции, прежде чем продавать их. Порядок имеет значение.
Но я все еще хотел использовать свои математические методы!
Итак, я подумал: «Хорошо, давайте предположим, что первая цена - это наша минимальная цена, наша цена покупки, а затем просто найдем Math.max () из остальной части массива, которая будет нашей ценой продажи».
Неа. Этот подход может работать в некоторых случаях, но полностью упускает меньшее число, которое может появиться в массиве после 0-го индекса (но все же до максимума из нарезанного массива).
Хорошо, нам просто нужно пройтись по циклу и убедиться, что наш «min» действительно является нашим минимумом, прежде чем мы вернем разницу.
Внезапно проблема показалась не такой простой. И я понял, что когда я наполнял свой набор инструментов встроенными методами, эти новые инструменты стали моим Молотком Маслоу. Я хотел использовать их, даже когда они не подходили для работы.
Хорошо, теперь давайте забудем об объекте Math - забудьте об определении минимума или максимума нашего массива.
Давайте посмотрим на каждое значение, начиная с первого в массиве (с индекса 0), и предположим, что это наша «цена покупки» или «минимальная» цена. Затем мы найдем максимально возможную прибыль, вычтя ее из всех остальных значений в массиве.
Как только мы получим наибольшую прибыль от этой «покупки», сохраните ее в переменной, перейдите к следующему значению в массиве и предположите, что IT - наша цена «покупки», сравнивая ее с каждым значением, которое приходит после и так далее. Это начинает звучать как вложенные циклы ...
Это решение будет работать, но оно очень неэффективно. Такой метод грубой силы является обычным «первым подходом», но оставляет место для улучшения. Мы сравниваем каждое число с любым другим числом. С большим O, равным n², мы можем добиться большего.
Для лучшего решения требуется всего пара переменных, один цикл for и несколько условных операторов.
Вот один из подходов:
Инициализируйте первое значение как «минимум» или «покупка», так как это ваша самая первая возможность купить.
Затем мы инициализируем максимальную прибыль равной -1, так как это ожидаемый доход, если прибыль не будет найдена.
А теперь простой цикл for. В этом случае нам не нужно перебирать весь массив - мы просто начнем с первого индекса. (0-й индекс - это цена покупки и никогда не может быть ценой продажи, поэтому нет необходимости оценивать его как таковую.)
Вот код:
Для меня главный вывод в решении проблемы фондового рынка заключался в том, что иногда возможность избавиться от своего арсенала JavaScript так же важна, как и его создание в первую очередь.
