B6. 學妹表示太難不想去建中上課（TooHard）

Problem Statement

建電面試 - 學術專用題 pG：

你會比較想教難一點的東西還是入門一點的東西，為什麼？

那如果今天你的對幹或是其他學術跟你說他覺得這個別人會聽不懂，你會怎麼辦？

\(Repkironca\) 剛寫完物理，他發現自己不管怎麼跑，永遠都脫離不了簡諧運動的魔掌。因此，所以他決定過來出學術上機考的題目，以噁心學弟妹為樂。

然而，剛剛的物理已經把他腦細胞燒光，導致她壓根想不到題敘。他想出的題目，用白話文來說是這樣的：

給定 \(N\) 個數字 \(x\) 排成一列，今天我要在裡面取出一些數字保留，並盡可能使我保留的數字總和最大。然而，在取數字時有一項限制：我必須一次拿走 3 個相鄰的數字，且保留中間那個。至於左右兩個數字，會被無情地捨棄。當場上數字不到 3 個時，就不能再行拿取。

舉例來說，如果 \(N = 6\)，這是一個可能的情況：2 4 5 9 7 6。你可以先拿走 4 5 9，並且保留 5，此時場上還剩下 2 7 6。接著再拿走 2 7 6，並且保留 7。

你保留的數字總和是 5 + 7 = 12，顯然，這並不是最佳解。

正當 \(Repkironca\) 思考著這道題該怎麼寫時（對，他自己還沒想到正解，超級糟糕），一道熟悉的聲音響起：

＂你出得太難了吧，輸光，大家都不會寫＂

原來，當初面試中的那個 其他學術，aka 嗯嗯出現了。他告訴 \(Repkironca\) 一個殘忍的事實：

這下好了，大家會不會寫，\(Repkironca\) 根本不在意。但如果沒有學妹要打比賽，這會危及到建北電資的核心價值。此時，嗯嗯又冷不及防地補了一句：

＂任何一個有常識跟良知的人，都知道在出題前，自己必須先解出答案吧＂

哇咧，不愧是嗯嗯，她精準打到了 \(Repkironca\) 的痛點。無奈之下，\(Repkironca\) 把題目簡單化了一些：

給定 \(N\) 個數字 \(x\) 排成一列，今天我要在裡面選擇一些數字，並盡可能使我選擇的數字總和最大。然而，在選數字時有一項限制：一旦我選擇第 \(K\) 個數字，則第 \(K-1\) 與第 \(K+1\) 個數字就不能再被選擇了。當然，如果你選擇的數字恰好在邊界，就只有一側的數字會受到影響。

你不見得要將數字選完，如果你想要，甚至可以一個數字都不選，總和就會是 0

一個數字被選擇後仍然待在原地，不會被移出陣列。舉一個 N = 6 的例子 2 4 5 9 7 6，你可以選擇 2 5 7，這種選法的總和是 14。又或者，你可以選擇 4 9 6，這種選法的總和是 19，顯然後者比較理想。

＂這樣可以了嗎？＂\(Repkironca\) 問道
＂看起來不錯，至少這題我會寫＂ 嗯嗯滿意地回答
＂噢好耶，小雞芒果拉瑪冰＂

嗯對，事情至此結束。\(Repkironca\) 回去寫他的物理，他剛剛把問題丟給姜姜，現在知道解答了。而嗯嗯跑去吃全家霜淇淋，不知道是這星期的第幾支，反正目前的白葡萄口味她吃得很開心。

不過有個小問題：\(Repkironca\) 跟嗯嗯兩人，都沒有把解答說出來。為了不讓這題變成費馬大定理，螢幕前的你能夠幫忙寫出這題的 AC 解，拯救整個資訊界嗎？

Input Format

一開始吃進一個正整數 \(N\)，代表總共有多少數字
下一行有 \(N\) 個數字 \(x\) 排成一列，中間以空格分開，意義請見題敘

  • \(1 \leq N \leq 10^6\)
  • \(-10^9 \leq x \leq 10^9\)

Output Format

請輸出你所選擇的數字總和，盡可能讓其最大

Sample

Input

6
2 4 5 9 7 6

Output

19

Input

6
7 -3 0 14 -18 -5

Output

21

Scoring

每個 Subtask 獨立計算，取聯集，滿分 100 分
若未特別提及，測資範圍均與題敘吻合

  • Subtask.1（8%）保證 \(\forall x_i×x_{i+1} \leq 0 \land 2 \leq N \leq 1000\)
  • Subtask.2（7%）保證 \(1 \leq N \leq 10\)
  • Subtask.3（26%）保證 \(0 \leq x_i \leq 10^9 \land 2 \leq N \leq 1000\)
  • Subtask.4（59%）無額外限制

Hint

tags: 2023建北電資學術上機考
Select a repo