2
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ If $M$ is a constant, then $O(N)$ or at most $O(N^2)$ should be feasible by dynamical programming. Have you tried that? $\endgroup$ – Apass.Jack Mar 18 at 22:54
  • $\begingroup$ thanks for your reply. I edited the question, I assumed that M is a constant because M has a much lower value rather than N. in fact, M is in the order of 10^2 and for example, exponential complexity base on M is not good. by considering M as a non-constant value, what is the complexity order of the proposed dynamic programming approach? I would be thankful if you give me more hint. $\endgroup$ – Ehsan Mar 19 at 7:28
  • $\begingroup$ Unfortunately, I don't have any ideas on how to split the problem into subproblems and use DP approach. If you give me a hint about subproblems, I can work on it and rewrite the question more accurately. $\endgroup$ – Ehsan Mar 19 at 17:37
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ This approach does not specialize to the given linear solution when $M=1$, which suggests that some significant improvement should be possible. $\endgroup$ – Apass.Jack Mar 19 at 18:50
  • $\begingroup$ Thank. It's a nice solution, now I have some idea to work on my question. But I am a little bit confused with this part of your solution: "$dp2[m][n]$ is the larger of $dp2[m−1][n]$ and $dp[m][n]$". Does it mean that $dp2[m][n] = max(dp2[m−1][n], dp[m][n])$ ? if so, I can't understand the reason of it's correctness. I think some values must be added to $dp2[m−1][n]$ and then get the maximum. $\endgroup$ – Ehsan Mar 20 at 9:53
  • $\begingroup$ One way for computing $dp2[m][n]$ is to find the maximum value of $dp[m-1][x] + f(x)$ for $x \leq n$, where $f(x)$ means optimum value for finding largest (just one) rectangle between x-th and n-th bar. It seems that it has the complexity of $O(MN^2)$. Is it a good way? $\endgroup$ – Ehsan Mar 20 at 10:01
  • $\begingroup$ My typo, It should have been "$dp2[m][n]$ is the larger of $dp2[m][n-1]$ and dp[m][n]$". Please come to chat.stackexchange.com/rooms/2710/computer-science for a chat. $\endgroup$ – Apass.Jack Mar 20 at 13:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.