Problem 1328. -- [Usaco2003 Open]Jumping Cows

1328: [Usaco2003 Open]Jumping Cows

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 62  Solved: 37
[Submit][Status][Web Board]

Description

一天,主人买来N个BONE(1 <= N <= 150,000),从左向右排成一排. 狗狗想把所有的BONE全吃了,但这似乎不太可能的.主人说:狗狗,你做为我的宠物,应该要足够的聪明伶俐,睿智过人,玉树临风.我来考一下你.这里每一个BONE都有一个分数K(1<=K<=500)。你从第一个BONE开始.对于每个BONE,你可选也可不选。选择多少个也随便你但你必须从第一个开始选,从左选到右。当你选好BONE后。我会将第一个BONE的分值乘上一个1,第二个则乘上一个-1第三个又是一个1,第四个又是一个-1.然后再加起来。我希望总分值最大。你应该如何选呢

Input

第一行给出一个数字N,代表有多少块Bone.
下面N行,每行一个数字,代表每块Bone的权值。

Output

如题

Sample Input

8
7
2
1
8
4
3
5
6

Sample Output

17
说明:取7 1 8 3 6,得到+7-1+8-3+6=17。

HINT

Source

[Submit][Status]