题目内容

小华之前玩过一个游戏，在横轴上放了 $n$ 个相邻的矩形，每个矩形的宽度是 $1$ ，而第 $i(1≦i≦n)$ 个矩形的高度为 $h_i$ ，这 $n$ 个矩形构成了一个直方图，在直方图中找出能够勾勒出来的矩形的最大面积。

这个游戏小华已经玩得很腻了，于是小华就想增加一下难度，现在有 $1$ 次交换任意 $2$ 个矩形的操作，请问在交换后，能够勾勒出的最大的短形面积能达到多少呢?

输入描述

在横轴上有 $n$ 个宽度均为 1 的相邻矩形，第 $i$ 个矩形的高度为 $h_i$ ，它们共同构成了一个直方图。普通的「最大矩形面积」问题是：在不改变顺序的前提下，找到可以完全覆盖在直方图之下的、面积最大的矩形。

本题在此基础上允许你 执行一次任意两根柱子高度的交换，问：在进行至多一次交换之后，能得到的最大矩形面积是多少？

▶️