情人节脱单大法

情人节脱单大法

题目背景

总所周知!王赞博有了女朋友却谁也不知道。但是王赞博有“暗恋”对象,于是就被王赞博的女朋友给知道了,但是呢,王赞博的女朋友是一个热爱画画的温柔又可爱的女孩纸,于是她决定把王赞博大卸两块,没错是两块!!

题目描述

王赞博呢,他的长度为 n,并且每个单位长度都有一个相对应的重量,他的小女朋友希望将王赞博切成两部分后,两个部分中的最大重量之差的绝对值最大(显然两个部分均不能为空啊),她呢觉得很惆怅,不知道该怎么切最好,所以想让在座的各位大佬来想想办法。

输入输出格式

输入格式:

第一行为一个n(2 <= n <= 1e5),表示王赞博的长度,第二行为n个数,表示王赞博每个单位长度的重量(0 <= a[i] <= 1e6)。

输出格式:

输出切成两部分后,每部分的重量的最大值之差的绝对值最大是多少。

输入输出样例

输入样例1:

4
1 2 3 4

输出样例1:

3

说明

对于样例:

4

1 2 3 4

那么一共有 3 种切法,分别是:

第一部分为 { 1 }, 第二部分为{ 2,3,4 },此时两部分的最大值之差的绝对值为 3

第一部分为 { 1,2 }, 第二部分为{ 3, 4 },此时两部分的最大值之差的绝对值为 2

第一部分为 { 1,2,3 }, 第二部分为{ 4 },此时两部分的最大值之差的绝对值为 1

所以答案为3.

信息

难度
10
分类
(无)
标签
(无)
递交数
4
已通过
0
通过率
0%
上传者