Пояснение и псевдокод:
Чтобы решить эту проблему, во-первых, мы используем подход алгоритм грубой силы. мы попробуем все возможные прибыли, которые мы можем получить от данных значений, и выберем самое высокое. Чтобы рассчитать максимальную прибыль, которую вы можете получить от каждой сделки.
- Создайте переменную
maxProfit
для хранения максимальной прибыли - Прокрутите массив дважды, чтобы получить цену покупки и цену продажи.
- Рассчитайте прибыль, вычитая
buyPrice
изsellPrice
. - Если значение profit больше, чем значение maxProfit, установите maxProfit равным прибыли.
- вернуть
maxProfit
Вот разбивка того, как код вычисляет и возвращает максимальную прибыль, используя два цикла;
Анализ сложности
- Временная сложность: O(n²), где n — длина массива цен.
- Пространственная сложность: O(1). были созданы только две переменные. maxProfit и прибыль
Лучший подход с использованием цикла One For;
из приведенного выше объяснения вы заметите, что для расчета максимальной прибыли используется шаблон. Вместо того, чтобы пересчитывать все значения друг с другом, мы можем вместо этого отслеживать минимальную цену и вычитать ее из продажных цен следующим образом.
Пояснение и псевдокод:
- создайте переменную для хранения максимальной цены
- создайте еще одну переменную для отслеживания минимальных цен и установите для нее первое значение в массиве
- прокручивать массив цен, начиная с индекса 1, в качестве цены продажи
- чтобы получить прибыль, нужно вычесть
minPrice
из цены продажи. - Если прибыль больше, чем максимальная прибыль, замените значение MaxProfit значением прибыли.
в других случаях, чтобы рассчитать прибыль для других значений, проверьте, меньше ли текущее значение, которое является sellingPrice, чем значение minPrice
. Если это так, установите текущее значение, которое является продажной ценой, на minPrice
.
- вернуть максимальную прибыль
Вот разбивка того, как код вычисляет и возвращает максимальную прибыль, используя один цикл for;
Анализ сложности
- Временная сложность: O(n), где n — длина массива цен.
- Пространственная сложность: O(1). были созданы только две переменные. maxProfit и minPrice
Надеюсь, вам было легко понять это объяснение. Удачного кодирования!