Skip to content

1400: 盖大楼

题目

题目描述

Sakits 要建楼啦!

现在东川路上有 $n$ 个地块排成一排,每个地块有一个购买的价格 $a_i$。Sakits 打算在路上挑出 $i$ 和 $j$ 两个地块盖楼。

为了彰显他的财大气粗,Sakits 打算尽量挑贵的地块盖楼——就是说,他想让 $a_i + a_j$ 尽量大。

另外,他还不想让两栋楼离得太近。换句话说,他还想要 $|i - j|$ 尽量大。

为了满足 Sakits 的两个愿望,地产公司想出了一个绝妙的主意:找到两个地块,使得这两个地块的“价值” $(a_i+a_j) \cdot |i - j|$ 是这条路上最大的,不就可以了吗?

可惜地产公司的电脑太差了,算不出最大的价值是多少...... 你能帮帮 Sakits 吗?

输入格式

第一行一个整数 $n$,表示地块的数量

接下来一行 $n$ 个整数,第 $i$ 个整数 $a_i$ 表示 $i$ 号地块的价格

输出格式

一行一个整数,表示挑出的两个最大地块的价值。

样例输入

text 5 8 3 6 3 1

样例输出

text 36

数据范围

对于 $10 \%$ 的数据,$1 ≤ n ≤ 1000$;
对于 $50 \%$ 的数据,$1 ≤ n ≤ 100000$,保证数据随机生成;
对于 $100 \%$ 的数据,$1 ≤ n ≤ 1000000$,$1 ≤ a_i ≤ 1000000$。

Oops! 本题目还没有解答!

助教老师们编题的速度,已经超过了解题的速度!

OJ翻了一新,但本解答集还大多用的是2017-2019级,甚至更早的同学们贡献的答案。

如果你已经AC了,可以的话,请您参考添加页面,与大家一起分享你的题解!