Описание испытания

Вам дан массив prices, где prices[i] — цена данной акции на ith день.

Вы хотите максимизировать свою прибыль, выбрав один день для покупки одной акции и выбрав другой день в будущем для продажи этой акции.

Возвратите максимальную прибыль, которую вы можете получить от этой транзакции. Если вы не можете получить прибыль, верните 0.

Пример 1:

Input: prices = [7,1,5,3,6,4]
Output: 5
Explanation: Buy on day 2 (price = 1) and sell on day 5 (price = 6), profit = 6-1 = 5.
Note that buying on day 2 and selling on day 1 is not allowed because you must buy before you sell.

Пример 2:

Input: prices = [7,6,4,3,1]
Output: 0
Explanation: In this case, no transactions are done and the max profit = 0.

Первое решение (временная сложностьO(n²)):

var maxProfit = function (prices) {
  let margin = 0;
  for (i = prices.length - 1; i > 0; i--) {
    for (k = 0; k < i; k++) {
      if (prices[i] - prices[k] > margin) {
        margin = prices[i] - prices[k];
      }
    }
  }
 
  return margin;
};

Временная сложность данного кода равна O(n²), где n — длина входного массива prices. Код использует структуру вложенного цикла для сравнения каждой пары цен и расчета максимальной прибыли. Внешний цикл повторяется от prices.length - 1 до 1, а внутренний цикл повторяется от 0 до i.

Для каждой пары цен код проверяет, превышает ли разница между prices[i] и prices[k] текущую margin. Если это так, margin обновляется.

ПРИМЕЧАНИЕ. Этой наихудшей временной сложности можно избежать, используя один цикл. Другое решение приведено ниже:

Второе решение (временная сложностьO(n)):

var maxProfit = function (prices) {
  let leftIndex = 0,
    rightIndex = 1,
    maxMargin = 0;
  while (rightIndex < prices.length) {
    if (prices[leftIndex] < prices[rightIndex]) {
      let profit = prices[rightIndex] - prices[leftIndex];
      maxMargin = Math.max(maxMargin, profit);
    } else {
      leftIndex = rightIndex;
    }
    rightIndex++;
  }
  return maxMargin;
};

Временная сложность обновленного кода равна O(n), где n — длина входного массива prices.

В коде используется один цикл, который перебирает массив prices слева направо. Он поддерживает два индекса, leftIndex и rightIndex, которые представляют начальную и конечную точки окна потенциальной прибыли. Изначально для leftIndex установлено значение 0, а для rightIndex установлено значение 1.

На каждой итерации код проверяет, превышает ли цена rightIndex цену leftIndex. Если это так, он рассчитывает прибыль, вычитая цену leftIndex из цены rightIndex. Затем код обновляет maxMargin максимальным значением между текущим maxMargin и рассчитанной прибылью.

Если цена на rightIndex не выше цены на leftIndex, это означает, что открытие нового окна прибыли с текущей позиции приведет к меньшей прибыли. В этом случае код обновляет leftIndex до rightIndex, чтобы открыть новое окно потенциальной прибыли.

Цикл продолжается до тех пор, пока rightIndex не достигнет конца массива prices.

Удачного кодирования!!