A - Operations on a Stack

Contest Duration: 2025-03-09(Sun) 12:00 - 2025-03-09(Sun) 14:00 (local time) (120 minutes) Back to Home

A - Operations on a Stack Editorial

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : $400$ 点

問題文

長さ $N$ の整数列 $(A_1, A_2, \ldots, A_N)$ が与えられます。また、列 $S$ があり、 $S$ ははじめは空列です。

$i = 1, 2, \ldots, N$ の順に、それぞれの $i$ について、下記の $2$ つの操作のうちちょうど $1$ つを行います。

$S$ の末尾に $A_i$ を要素として追加する。
$S$ の末尾の要素を削除する。ただし $S$ が空のときは、この操作を行うことを選択できない。

すべての操作を終えた後の、 $S$ の要素の総和としてあり得る最大値を出力してください。

制約

$1 \leq N \leq 2 \times 10^5$
$-10^9 \leq A_i \leq 10^9$
入力はすべて整数

入力

入力は以下の形式で標準入力から与えられる。

 $N$ 
 $A_1$   $A_2$   $\ldots$   $A_N$

出力

答えを出力せよ。

入力例 1Copy

Copy

6
3 -1 -4 5 -9 2

出力例 1Copy

Copy

$S$ が空列である初期状態から、下記の通りに操作を行うことを考えます。

$i = 1$ について、 $S$ の末尾に $A_1 = 3$ を追加する。その結果、 $S = (3)$ となる。
$i = 2$ について、 $S$ の末尾に $A_2 = -1$ を追加する。その結果、 $S = (3, -1)$ となる。
$i = 3$ について、 $S$ の末尾の要素を削除する。その結果、 $S = (3)$ となる。
$i = 4$ について、 $S$ の末尾に $A_4 = 5$ を追加する。その結果、 $S = (3, 5)$ となる。
$i = 5$ について、 $S$ の末尾に $A_5 = -9$ を追加する。その結果、 $S = (3, 5, -9)$ となる。
$i = 6$ について、 $S$ の末尾の要素を削除する。その結果、 $S = (3, 5)$ となる。

このとき、すべての操作を終えた後の $S$ の要素の総和は、 $3 + 5 = 8$ であり、これがあり得る最大値です。

入力例 2Copy

Copy

1
-1

出力例 2Copy

Copy

-1

$S$ が空のときは必ず、要素を追加する方の操作を選ばなければならないことに注意してください。

入力例 3Copy

Copy

20
-14 74 -48 38 -51 43 5 37 -39 -29 80 -44 -55 59 17 89 -37 -68 38 -16

出力例 3Copy

Copy

Score : $400$ points

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.

Sample Input 1Copy

Copy

6
3 -1 -4 5 -9 2

Sample Output 1Copy

Copy

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.

Sample Input 2Copy

Copy

1
-1

Sample Output 2Copy

Copy

-1

Note that if $S$ is empty, you must choose to append an element.

Sample Input 3Copy

Copy

20
-14 74 -48 38 -51 43 5 37 -39 -29 80 -44 -55 59 17 89 -37 -68 38 -16

Sample Output 3Copy

Copy