No.2854 -1 Subsequence
dyktr_06
ryota2357
問題文最終更新日: 2024-08-25 02:19:00
English (AI translation)
-1 Subsequence
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Show the original
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Show the original
yukicoder contest 442 MMA Contest 019
(順位表)
の他の問題:
Problem Statement
You are given a sequence $A$ of length $N$.
Define the score of a non-empty sequence $B$ as follows.
- Letting $K$ be the length of $B$, the score is $\displaystyle \sum_{i = 1}^{K} B_i \times (-1)^{i}$
You may choose exactly $1$ non-empty subsequence of $A$, not necessarily contiguous, and obtain the score of that subsequence.
Find the maximum possible score you can obtain.
Constraints
- $1 \leq N \leq 2 \times 10^{5}$
- $| A_i | \leq 10^{9}$
- All inputs are integers.
Input
The input is given from standard input in the following format.
$N$
$A_1$ $A_2$ ... $A_{N}$
Output
Output the answer to the problem on a single line.
Sample
Sample 1
Input
5 -3 -2 1 2 3
Output
6
If you choose $(-3, 3)$ as the subsequence, the score is $-3 \times (-1)^1 + 3 \times (-1)^2 = 6$, and this is the maximum.
Sample 2
Input
8 -887791923 -540126285 688481141 -734932412 -109240649 225669457 786200001 72702954
Output
3097405477
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。