b052: 減法遊戲
Tags : DP
Accepted rate : 1人/1人 ( 100% ) [非即時]
評分方式:
Tolerant

最近更新 : 2020-09-01 00:09

Content

 

「欸欸,我們來玩減法遊戲好不好?」

「不要。」

「......」

「......」

「總之呢~我會有n個數字排成一排,你可以選擇其中一小段數字{al,al+1,al+2...ar} ,你的分數會是 (al - al+1 - al+2 ... - ar ),然後我們比較誰的分數高就贏了!怎麼樣,簡單吧。」

「滾啦我要專心念書了。」

「那我先囉。」

「......」

 

Input

第一行是n (n <= 500000),第二行有n個整數(絕對值 <= 500000),表示一排數字。

Output

輸出可能的最高分數

Sample Input
//case 1
8
5 -3 6 -2 -4 6 -1 -7

//case 2
3
-15 -5 -6

//case 3
6
100000 -100000 -100000 100000 -100000 -100000
Sample Output
//case 1
14

//case 2
1

//case 3
400000
測資資訊:
記憶體限制: 64 MB
公開 測資點#0 (5%): 1.0s , <1K
公開 測資點#1 (5%): 1.0s , <1K
公開 測資點#2 (5%): 1.0s , <1K
公開 測資點#3 (5%): 1.0s , <1M
公開 測資點#4 (5%): 1.0s , <1M
公開 測資點#5 (10%): 1.0s , <1M
公開 測資點#6 (15%): 1.0s , <1M
公開 測資點#7 (20%): 1.0s , <10M
公開 測資點#8 (20%): 1.0s , <10M
公開 測資點#9 (9%): 1.0s , <10M
公開 測資點#10 (1%): 1.0s , <1K
Hint :

至少要選一個數字喔~

Tags:
DP
出處:
臺中一中電腦資訊研究社 [管理者:
TCIRC ($\mathbb{TCFSH}\mathtt{Computer}\mathsf{Information}\mathit{Club}$)
]


ID User Problem Subject Hit Post Date
沒有發現任何「解題報告」