Leetcode.com, задача №121. "Лучшее время для покупки и продажи акций"

!!НАШ БЛОГ ПЕРЕЕХАЛ!!

Мы создали свой сайт! Все материалы, опубликованные в этом блоге, переехали туда.

Наш новый сайт maddevelop.ru

А данную статью вы можете найти по ссылке

Условие

Дан массив значений стоимости акций. Разрешено сделать одну транзакцию: покупка и продажа. И только в таком порядке. Необходимо вычислить максимальную прибыль, которую можно получить. В противном случае вернуть 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, немедленно запускающее следующую итерацию.

Ещё больше интересной информации на нашем Telegram канале.