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

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

Предположим, что у нас есть массив цен на акции. Придумайте алгоритм, который выводит массив с максимальной прибылью за каждый день i в массиве. Так, например, если бы у нас был массив 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 3
arrays algorithm time-complexity brute-force

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, который содержит ваши цены в виде целых чисел.

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

Это может быть сделано в одном линейном сканировании, поэтому сложность равна 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 - го дня.

0