Here's my gut instincts.
For the uniform interval case: take the two smallest y values and assign them to the endpoints. Assign the rest of the y values any way you want.
For the non-uniform interval case: You have two options: brute force search, or some sort of heuristic.
Option 1: brute force search will be , where is the number of points. This is not good performance! The algorithm would like like this:
Code:
Largest_Area = - infinity;
Best_Permutation = Y;
For each permutation of the Y set:
compute new_area = trapezoidal rule for non-uniform intervals;
If new_area > Largest_Area Then
Best_Permutation = Current_Permutation;
Largest_Area = new_area;
End If
End For
Output Largest_Area, Best_Permutation
Option 2: heuristics. Here's one strategy: rank the intervals according to width. Rank the y values according to value. Perform a match-up of intervals to y-values in this order subject to the following constraints:
1. I think you want to have all the trapezoids as close to being squares as possible. You might try minimizing the least squares formula that follows:
I don't know how you would do this, however. What you're changing is the permutation of the Y set.
This formula represents a measure of how far off from being square all the trapezoids are.
2. There must be continuity from one interval to the next. That is, only one y value may be chosen at the intersection of two intervals.
Example: X = {0,1,4,6,7}, Y={1,1,2,4,5}.
Ranking of x-intervals:
[1,4]
[4,6]
[0,1]
[6,7]
Ranking of y-values:
5
4
2
1
1
Matchup:
y = 5 and y = 4 correspond to [1,4]. Choose y = 4 and y = 2 to correspond with [4,6]. Choose y = 2 and y = 1 to correspond with [6,7]. Finally, choose y = 1 and y = 5 to correspond with [0,1]. That is, the Y set permutation is {1,5,4,2,1}.
Now this algorithm, as is, will not necessarily provide you with the absolute maximum sum. It will get close. As a matter of fact, the assignment Y = {1,4,5,2,1} gives a slightly higher area.
I think you generally want to assign larger y values to larger intervals. However, as I have already pointed out, there are further optimizations to be done. You might want to think about choosing the higher y values to be closer to the "x center of mass", which you could define as follows:
Conclusion: the non-uniform case is a difficult problem. I'm not sure if I know of a sure-fire way to find the global max other than brute-force search. The algorithms I've outlined here will get you a good value, I think. But it's difficult. With lots of intervals, the problem can get very challenging indeed. You might consider evolutionary algorithms in order to avoid local maximums. Or an annealing algorithm. Here's a fantastic book that has loads of information on heuristics: How to Solve It: Modern Heuristics, by Michalewicz and Fogel. This book is simply a fun read. I'd highly recommend it.