823 . RGB

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

dbGIs
這題出的好!唐可可給你一個讚

User's AC Ratio

100.0% (3/3)

Submission's AC Ratio

100.0% (3/3)

Tags

apcsc apcsc-dp

Description

某天 bb 拿到了一個長度 $N$ 的序列 $v_1, v_2, \cdots, v_N$，這個序列裡面的數字 有正有負也有可能有零，而 bb 想用紅、綠、藍三種顏色幫這個序列上色。為了美觀，每個數字都必須被標上顏色，而且序列中任兩個相鄰的數字必須要被標上不同的顏色。由於 bb 喜歡綠色且討厭紅色，他覺得這個序列上色之後的價值是標上綠色的數字的總和扣掉標上紅色的數字的總和。請問在滿足上述的條件下，這個序列上色後價值可以變成多高呢？

Input Format

輸入的第一行有一個正整數 $N$，代表序列的長度。
第二行有 $N$ 個整數 $a_1, a_2, \cdots a_N$，代表序列的數值。

  • $1 \leq N \leq 10^ 6$
  • $−10000 \leq a_i \leq 10000$

Output Format

輸出只有一行，代表上色之後這個序列的最高可能價值。

Sample Input 1

10
9 -3 7 8 3 -5 -7 -9 6 4

Sample Output 1

42

Hints

Problem Source

NPSC 2019 國中組

Subtasks

No. Testdata Range Constraints Score
1 0 範例測資 0
2 0~25 無額外限制 100

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 524288 65536 1 2
1 1000 524288 65536 2
2 1000 524288 65536 2
3 1000 524288 65536 2
4 1000 524288 65536 2
5 1000 524288 65536 2
6 1000 524288 65536 2
7 1000 524288 65536 2
8 1000 524288 65536 2
9 1000 524288 65536 2
10 1000 524288 65536 2
11 1000 524288 65536 2
12 1000 524288 65536 2
13 1000 524288 65536 2
14 1000 524288 65536 2
15 1000 524288 65536 2
16 1000 524288 65536 2
17 1000 524288 65536 2
18 1000 524288 65536 2
19 1000 524288 65536 2
20 1000 524288 65536 2
21 1000 524288 65536 2
22 1000 524288 65536 2
23 1000 524288 65536 2
24 1000 524288 65536 2
25 1000 524288 65536 2
Submit
Back to Top