Максимізація прибутку#11480

Максимізація прибутку (Розбір)

Нехай $p_{0}, p_{1}, ..., p_{n - 1}$ p_0, p_1, ..., p_{n-1} — це ціни акцій по днях. Обчислимо $d p_{i} = ma x (p_{i}, ..., p_{n - 1})$ dp_i = max(p_i, ..., p_{n-1}) — максимум на суффіксах масиву $p$ . Якщо в $i$ -й день купити акцію за ціною $p_{i}$ p_i, то потім вигідно продати її можна буде за найвищою ціною $d p_{i}$ dp_i, отримавши прибуток $d p_{i} - p_{i}$ dp_i - p_i. Залишається обчислити загальний прибуток, рівний

i = 0 \sum n - 1 (d p_{i} - p_{i})

\sum_{i=0}^{n - 1} (dp_i - p_i)

Приклад

Розглянемо другий тест. Обчислимо максимум на суффіксах масиву цін акцій.

Наприклад, у перший день купуємо акцію за $p_{1} = 2$ p_1 = 2, і продаємо її потім за $d p_{1} = 9$ dp_1 = 9 (продаж відбудеться на третій день).

Загальний прибуток складе $4 + 7 + 3 + 0 + 7 + 2 + 3 + 0 + 0 = 26$ 4 + 7 + 3 + 0 + 7 + 2 + 3 + 0 + 0 = 26.

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

Читаємо вхідні дані.

scanf("%d", &n);
p.resize(n);
dp.resize(n);
for (i = 0; i < n; i++)
  scanf("%d", &p[i]);

Обчислюємо $d p_{i} = ma x (p_{i}, ..., p_{n - 1})$ dp_i = max(p_i, ..., p_{n-1}).

dp[n - 1] = p[n - 1];
for (i = n - 2; i >= 0; i--)
  dp[i] = max(p[i], dp[i + 1]);

Обчислюємо загальний прибуток $r es$ . У $i$ -й день купуємо акцію за ціною $p_{i}$ p_i та потім продаємо її за $d p_{i}$ dp_i, отримавши прибуток $d p_{i} - p_{i}$ dp_i - p_i.

res = 0;
for (i = 0; i < n; i++)
  res = res + dp[i] - p[i];

Виводимо відповідь.

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

Python реалізація

Читаємо вхідні дані.

n = int(input())
p = list(map(int, input().split()))

Обчислюємо $d p_{i} = ma x (p_{i}, ..., p_{n - 1})$ dp_i = max(p_i, ..., p_{n-1}).

dp = [0] * n
dp[n - 1] = p[n - 1]
for i in range(n - 2, -1, -1):
  dp[i] = max(p[i], dp[i + 1])

res = 0
for i in range(n):
  res += dp[i] - p[i]

Виводимо відповідь.

print(res)