Given n tree heights find the cut that maximize the remaing tree height sum

user_19889135 0
Viewed 76

Given n non-negative numbers a_1, a_2, ..., a_n where each represents a point at coordinate (i, a_i), n vertical lines, representing trees height, are drawn such that the two endpoints of line i is at (i, a_i) and (i, 0).

The trees must be cutted in a way that the top of all of them are in a straigh line (not necessarily parallel to the ground). The first or the last tree can be removed, and in that case the root of the removed tree must align with the top of the other trees.

Whats the maximum sum of tree's height that can be achieved after the cut?

Example:

Input: 1.00 2.00 4.00 6.00

Output: 12.00

Image example

My best solution runs with time complexity O(N^2), where I assume that the best cut must include the top of two trees, and so for each top of tree I try to find the other one that maximizes the sum.

Any thoughts on how to solve this problem with time complexity lower than O(N^2)?

algorithm
2 Answers

As btilly observes, LP is a natural fit. We have two variables, the slope m and the intercept b, and constraints 0 ≤ m i + b ≤ ai. The objective is to maximize ∑i (m i + b). LPs with two variables can be solved in linear time.

A simple, randomized LP-solving algorithm due to Seidel is: if there are at most two constraints, just solve the problem somehow. Otherwise, remove a random constraint and solve the problem recursively. If the resulting solution doesn’t violate the removed constraint, then it’s optimal for the original problem. Otherwise, the removed constraint is tight; substitute and solve the one-variable problem.

user_21446690

Trick.

Suppose that i < j < k and (j, a_j) lies ABOVE the line from (i, a_i) to (k, a_k). Then the two trees that define the best cut does not go through (j, a_j) because it would have to go above one of the others.

So we can start from the left, and walk forward, eliminating trees from consideration until the area above the remaining ones is convex. That is we look at points 0, 1, and 2, decide whether to eliminate 1. Then take point 3 and see if we can eliminate point 2 on backwards. And so on.

This finishes in time O(n). And now I maintain that your optimal cut is from one of the remaining points to the next, or from 0 at either end to one of these points. Which can again be checked in time O(n) because if it is 2 consecutive remaining points we already know all points are above, and only need to check for being below 0 at either end.

This should take O(n).

user_5854110
Related