给定n个非负数a_1，a_2。。。，a_n，其中每个表示坐标(i，a_i(处的一个点，绘制表示树高度的n条垂直线，使得线i的两个端点位于(i，a_i(和(i，0(处。
树木的切割方式必须使其顶部呈直线(不一定与地面平行(。第一棵树或最后一棵树可以被移除，在这种情况下，被移除的树的根必须与其他树的顶部对齐。
砍伐后树的最大高度和是多少？
示例：
输入：1246.00
输出：12.00
图像示例
我的最佳解决方案以时间复杂性O(N^2(运行，其中我假设最佳切割必须包括两棵树的顶部，因此对于每棵树的每个顶部，我都试图找到另一个最大化总和的顶部。
关于如何解决时间复杂度低于O(N^2(的问题，有什么想法吗？
技巧。
假设i < j < k和(j, a_j)位于从(i, a_i)到(k, a_k)的线上。然后，定义最佳切割的两棵树不通过(j, a_j)，因为它必须高于另一棵树。
因此，我们可以从左边开始，向前走，将树木从考虑范围中删除，直到剩下的树木上方的区域凸起。也就是说，我们观察点0、1和2，决定是否消除1。然后取第3点，看看我们是否可以在后面消除第2点。等等。
这在时间O(n)结束。现在我坚持认为，你的最佳切割是从剩下的一个点到下一个点，或者从两端的0到其中一个点。这可以在时间O(n)中再次检查，因为如果是2个连续的剩余点，我们已经知道所有点都在上面，并且只需要检查两端是否低于0。
这应该需要O(n)。
正如btilly所观察到的，LP是一种自然拟合。我们有两个变量斜率m和截距b，约束条件0≤m i+b≤ai。目标是最大化∑i(mi+b(。LP具有两个变量可以在线性时间内求解。
Seidel提出的一种简单的随机LP求解算法是：如果最多两个约束，只是以某种方式解决问题。否则移除随机约束并递归地解决问题。如果得到的解决方案不会违反已删除的约束，那么它对于原始问题是最优的。否则，删除的约束为牢固的替代并求解一元问题。