AtCoder Regular Contest 194 (Div. 2)
翻译中…
Problem Statement
翻译中…
You are given an integer sequence of length $N$: $(A_1, A_2, \ldots, A_N)$. There is also a sequence $S$, which is initially empty.
翻译中…
For each $i = 1, 2, \ldots, N$ in this order, you perform exactly one of the following two operations:
翻译中…
- Append
$A_i$as an element to the end of$S$. - Delete the last element of
$S$. You cannot choose this operation if$S$is empty.
翻译中…
Print the maximum possible value of the sum of the elements of $S$ after all operations.
翻译中…
Constraints
翻译中…
$1 \leq N \leq 2 \times 10^5$$-10^9 \leq A_i \leq 10^9$- All input values are integers.
翻译中…
Input
翻译中…
The input is given from Standard Input in the following format:
翻译中…
N
A_1 A_2 \ldots A_N翻译中…
Output
翻译中…
Print the answer.
翻译中…
样例
Input #1
6
3 -1 -4 5 -9 2
Output #1
8
Starting from the initial state where $S$ is an empty sequence, consider the following operations:
- For $i = 1$, append $A_1 = 3$ to the end of $S$. Now, $S = (3)$.
- For $i = 2$, append $A_2 = -1$ to the end of $S$. Now, $S = (3, -1)$.
- For $i = 3$, delete the last element of $S$. Now, $S = (3)$.
- For $i = 4$, append $A_4 = 5$ to the end of $S$. Now, $S = (3, 5)$.
- For $i = 5$, append $A_5 = -9$ to the end of $S$. Now, $S = (3, 5, -9)$.
- For $i = 6$, delete the last element of $S$. Now, $S = (3, 5)$.
Here, the sum of the elements of $S$ after all operations is $3 + 5 = 8$, which is the maximum possible value.
Input #2
1
-1
Output #2
-1
Note that if $S$ is empty, you must choose to append an element.
Input #3
20
-14 74 -48 38 -51 43 5 37 -39 -29 80 -44 -55 59 17 89 -37 -68 38 -16
Output #3
369
题目信息
题面与样例版权归 AtCoder 及出题人所有；中文翻译由 AI 生成（CI 管线），如有出入请以原文为准。