Finding the largest possible area covered by M rectangle under a given histogram

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).

Edit:

@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$.

What are the subproblems of this problem when we try dynamic programming? Or what is the table?

The subproblems are finding $dp[m][n]$, the largest area possible by $m$ non-overlapping rectangle

• which are under the first $n$ leftmost bars and,

• the rightmost of which contains the $n$-th bar.

Let $dp2[m][n]$ be the the largest area possible by $m$ non-overlapping rectangle

• which are under the first $n$ leftmost bars and,

• the rightmost of which is not to the right of the $n$-th bar.

The answer is the maximum of $dp2[M][n]$, where $M\le n\le N$.

$dp[m][n]$ is the maximum of $dp2[m-1][n-1] + R_{n,1}$, $dp2[m-1][n-2] + R_{n,2}$, $\cdots$, $dp2[m-1][n-i] + R_{n,i}$, $\cdots$, where

• $R_{n,1}$ is the area of $n$-th bar

• $R_{n,2}$ is the area of the rectangle which expands the $n$-th bar and $(n-1)$-th bar horizontally and which contains $n$-th bar

• $\cdots$, where $R_{n,i}$ is the area of the rectangle which expands the $n$-th bar and $(n-i+1)$-th bar horizontally and which contains $n$-th bar.

$dp2[m][n]$ is the larger of $dp2[m][n-1]$ and $dp[m][n]$.

The initial values of the two tables and boundary relations should be easy to determine.

There might be optimization tricks to speed up computation besides the standard memorization. You can check whether this naive dynamic programming is fast enough, whose worst behavior is about $\Theta(MN^2)$, which happens when all bars are becoming shorter and shorter from left to right.

StackExchange Computer Science Q#105758, answer score: 2