Stock Maximize (Editorial)

Let p_0, p_1, ..., p_{n-1} be the stock prices over the days. Compute dp_i = max(p_i, ..., p_{n-1}) — the maximum on the suffixes of the array $p$. If we buy a share at price p_i on the $i$-th day, then in the future, we can profitably sell it at the highest price dp_i, gaining a profit of dp_i - p_i. We need to compute the total profit, which is equal to

Example

Let’s consider the second test. Compute the maximum on the suffixes of the array of stock prices.

For example, on the first day, we buy a share for p_1 = 2, and later sell it for dp_1 = 9 (the sale will occur on the third day).

The total profit will be 4 + 7 + 3 + 0 + 7 + 2 + 3 + 0 + 0 = 26.

Algorithm implementation

Read the input data.

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

Compute 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]);

Compute the total profit $res$. On the $i$-th day, we buy a share at price p_i, and later sell it for dp_i, gaining a profit of dp_i - p_i.

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

Print the answer.

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

Python implementation

Read the input data.

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

Compute 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])

Compute the total profit $res$. On the $i$-th day, we buy a share at price p_i, and later sell it for dp_i, gaining a profit of dp_i - p_i.

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

Print the answer.

print(res)