Hi all,

I have a question about the maximal convex hull polygon. You are given N points on a 2D plane. Each point has a value X. You want to find the convex polygon such that the sum of the value of the points on the perimeter of the polygon is maximal. Output the maximal sum.

I have an N^4 DP solution. as follows.

I choose a point i and sort all the other points around this point according to angle (similar to convex hull graham scan). Then, I write the following bottom-up dp formulation:

DP[B][A] stores the best convex polygon with the last two points at B and A.

Then I calculate DP[C][B] for all C such that C-B-A is convex and I-C-B is convex.

The DP has a runtime of N^3. As I am doing this DP for all vertices I, the algorithm has a total runtime of N^4.

However, I think that there is a better algorithm with a runtime of N^3. Does anyone know this algorithm? Can someone give me some hints?

Thanks in advance!