11613. Наилучшее время купить акции 2

 

Вам дан массив цен, где pricesi содержит цену имеющейся акции в i-ый день.

Каждый день Вы можете принять решение о покупке и/или продаже акций. Одновременно Вы можете владеть не более одной акцией.

Найдите максимальную прибыль, которую можно получить.

 

Вход. Первая строка содержит размер n (n ≤ 105) массива цен. Вторая строка содержит массив цен – n целых чисел, каждое не более 104.

 

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

 

Пример входа 1

Пример выхода 1

8

6 3 6 4 2 4 8 3

9

 

 

Пример входа 2

Пример выхода 2

4

5 5 3 2

0

 

 

РЕШЕНИЕ

жадный алгоритм

 

Анализ алгоритма

Рассмотрим как меняется стоимость акции каждый день. Если при переходе от дня i – 1 ко дню i ее стоимость растет, то разницу pricesi – pricesi – 1 включаем в общую прибыль.

 

Пример

Рассмотрим первый тест.

Прибыль составит 3 + 6 = 9.

 

Реализация алгоритма

Читаем входные данные.

 

scanf("%d", &n);

prices.resize(n);

for (i = 0; i < n; i++)

  scanf("%d", &prices[i]);

 

В переменной res вычисляем максимальную возможную прибыль.

 

res = 0;

for (int i = 1; i < prices.size(); i++)

 

Если при переходе от дня i – 1 ко дню i стоимость акции растет, то прибавляем к результату res прибыль prices[i] – prices[i – 1].

 

  if (prices[i] > prices[i - 1])

    res += prices[i] - prices[i - 1];

 

Выводим ответ.

 

printf("%d\n", res);

 

Python реализация

Читаем входные данные.

 

n = int(input())

prices = list(map(int, input().split()))

 

В переменной res вычисляем максимальную возможную прибыль.

 

res = 0

for i in range(1, len(prices)):

 

Если при переходе от дня i – 1 ко дню i стоимость акции растет, то прибавляем к результату res прибыль prices[i] – prices[i – 1].

 

  if prices[i] > prices[i - 1]:

    res += prices[i] - prices[i - 1]

 

Выводим ответ.

 

print(res)