Let $G=(V,E)$ be a complete finite graph with the vertices arranged in a circle. Each edge has a nonnegative weight, and we would like to find an efficient algorithm to find a subgraph of maximum total weight, which is a triangulation of the graph. A triangulation of the graph is a subgraph such that no edges cross and no edge can be added to the graph without adding a crossing edge.
Of course as you go around the circle every edge will be added since the weight is nonnegative and these edges can never cause a crossing.
I initially thought of a greedy algorithm, selecting the highest weight edges and eliminating all crossing edges, but of course that won't work. I also thought about eliminating least weight edges but it seems to me that would probably also not work for the same reason.
I also tried to think of a divide-and-conquer algorithm, perhaps sped up by dynamic programming or something. My only thought was to first pick a random vertex and then iterate through all edges, finding the maximum graph weight if the edge were included (by first finding the maximum weight triangulation on one side of the edge and then on the other). But the runtime then seems like it has the equation
$$ T(n)=[T(n-1)]+[T(4)+T(n-2)] + ... + [T(n-2)+T(4)]+[T(n-1)] $$
and that doesn't seem like it would be efficient.