给定树高数组求最大剩余树高和，求低于O(N²)的优化解法

给定n个非负数值a₁、a₂、…、aₙ，每个数值对应坐标点(i, aᵢ)，以此绘制n条垂直线代表树高——第i条线的两端点为(i, aᵢ)和(i, 0)。

需对树木进行切割，满足以下规则：

• 切割后所有保留的树的顶部必须处于同一直线（该直线无需与地面平行）
• 允许移除第一棵或最后一棵树，此时被移除树的根部需与其余树的顶部对齐

求切割后可获得的最大树高总和。

示例 #

输入：

1.00
2.00
4.00
6.00

输出：12.00
（注：最优方案为移除第一棵树，其余树的顶部连线经过第一棵树的根部(1,0)和第四棵树的顶部(4,6)，此时各保留树的高度分别为2、4、6，加上被移除树对应的0，总和为12.00）

现有解法 #

我当前的最优解法时间复杂度为O(N²)，核心思路是：最优切割的顶部连线必然经过两棵树的顶部（或是一棵的顶部与被移除树的根部），因此遍历每棵树的顶部，寻找另一棵能使总和最大的树，计算对应总和后取全局最大值。

提问 #

是否存在时间复杂度低于O(N²)的解法？

内容的提问来源于stack exchange，提问作者lavor