Finding the largest rectangular area possible in a given histogram is a well-known problem and have linear solution. I have a similar but different problem. In my problem, we have $M$ rectangles instead of one rectangle in the previous problem.
So, my problem is to find the largest area under a histogram by $M$ rectangles which don't have overlap with each other. It should be noted that the bottom edge of all rectangles should be on the vertical axis of the histogram.
Is there any tractable solution for large $N$ (where $N$ is the number of bars in the histogram).
@Apass.Jack suggested an approach with the complexity of $\Theta(MN^2)$, but after implementation, it needs some days for running! Is there any faster solution? For clarification, the value of $N$ is around $10^7$ and the value of $M$ is around $10^3$.