Максимальная прибыль от цен на акции

Я пытаюсь выяснить алгоритм "разделяй и властвуй" за O(nlogn) время, чтобы решить следующую реальную проблему -

Предположим, у нас есть массив цен на акции. Придумайте алгоритм, который распечатывает массив с максимальной прибылью за каждый день в массиве.

Так, например, если бы у нас был массив A = [4,6,2,1], наши дни представляли бы каждый индекс, и наш вывод был бы массивом со значениями [2,-4,-1,-1] с последний день был значением -A[i].

Я выяснил алгоритм грубой силы, который -

   1.) Scans the array for max after A[i]
   2.) Subtracts A[i] with max, places value in A', iterates to next day
   3.) When max reaches itself, repeat steps 1 & 2
   4.) When you reach the end, the value is -A[i], return

Кроме того, я запутался, если временная сложность алгоритма, описанного выше, будет o(n) или o(n^2). Самая большая стоимость в алгоритме - найти максимум, все остальное - o(1).

Может кто-нибудь, пожалуйста, помогите мне? Спасибо

Источник

2 ответа

Решение

Вы не хотите делить победителя здесь. Вы можете сделать это за линейное время (O(n)). Вот код в Java, но вы можете сделать это на любом языке:

int[] maxProfit = new int[prices.length];
int maxPrice = 0;
for (int i = prices.length - 1; i >= 0; i--) {
 maxProfit[i] = maxPrice - prices[i];
 maxPrice = Math.max(maxPrice, prices[i]);
}

Это предполагает, что у вас есть массив, prices, который содержит ваши цены в виде целых чисел.

Ключевым моментом здесь является то, что вы можете получить всю необходимую информацию, начиная с конца и возвращаясь назад.

Источник

Это можно сделать за одно линейное сканирование, поэтому сложность O(n), Прежде всего, давайте создадим массив максимумов M т.е. M[i] содержит максимальное количество, которое мы имеем после iдень

При обратном линейном сканировании это легко сделать:

У нас есть A = [4,6,2,1]Итак, на первом этапе мы берем последний элемент A который равен 1, и это максимальное значение на данный момент, так M[3] = 1тогда мы получим M[2] = max(M[3],A[2]) = 2тогда мы получим M[1] = max(M[2],A[1]) = 6наконец на последнем шаге мы получаем M[0] = max(M[1], A[0]) = 6,

Мы будем иметь M = [6,6,2,1], Этот алгоритм имеет O(n) сложности, то мы запустим еще один цикл для определения максимальной прибыли за каждый день, который также имеет O(n) сложность. Кстати, мы можем не хранить значения M и вместо хранения всего массива хранить только максимальное значение после iдень

Источник
Другие вопросы по тегам