Leetcode.com, задача №121. "Лучшее время для покупки и продажи акций"
Условие
Дан массив значений стоимости акций. Разрешено сделать одну транзакцию: покупка и продажа. И только в таком порядке. Необходимо вычислить максимальную прибыль, которую можно получить. В противном случае вернуть 0.
Пример №1
Входной массив: [7, 1, 5, 3, 6, 4]
Максимальная прибыль: 5
Объяснение: покупаем акции на второй день по цене 1, продаём - на пятый по цене 6, получается прибыль 5. Продавать по 7 мы не можем, т.к. сначала нужно купить акции.
Пример №2
Входной массив: [7, 6, 4, 3, 1]
Максимальная прибыль: 0
Объяснение: мы не можем в последующие дни купить по цене большей, чем продали в любой день.
Вариант №1 решения
Прежде всего, выразим задачу математически. От нас требуется найти max(price[j] - max[i]) при j > i.
Для начала попробуем простой перебор:
public class Solution { public int MaxProfit(int[] prices) { int delta; int maxProfit = 0; for (int i = 0; i < prices.Length; i++) { for (int j = i + 1; j < prices.Length; j++) { delta = prices[j] - prices[i]; if (delta > 0) maxProfit = Math.Max(maxProfit, delta); } } return maxProfit; } }
Главный недостаток перебора - время выполнения, которое в данном случае пропорционально n * (n - 1) / 2, где n - количество элементов в массиве. Поэтому временная сложность равняется квадрату количества элементов О(n * n).
Вариант №2
Для решения задачи лучшим способом достаточно одного прохода по массиву. При этом будем отмечать или перезаписывать наименьшее значение и вычислять по отношению к нему разницу со значениями последующих элементов.
public class Solution { public int MaxProfit(int[] prices) { if (prices.Length < 2) return 0; int maxProfit = 0; int minValue = prices[0]; for (int i = 1; i < prices.Length; i++) { if (prices[i] < minValue) { minValue = prices[i]; continue; } else { if (prices[i] - minValue > maxProfit) maxProfit = prices[i] - minValue; } } return maxProfit; } }
Временная сложность данного решения - О(n).
Так как на сайте можно смотреть лучшие по быстродействию решения, то свой первоначальный код я немного изменил.
В самом начале добавлена проверка на нулевой массив и массив с одним элементом:
if (prices.Length < 2) return 0;
После этой проверки инициализируется переменная minValue нулевым элементом массива. Это позволяет начать цикл for с первого элемента.
В самом цикле после нахождения минимального значения используется ключевое слово continue, немедленно запускающее следующую итерацию.