largest rectangle

[Script Coder]

Hello, I have been trying to crack this problem for about two hours and have gotten a few solutions that are too inefficient. Please help me.

Problem:
Given N (0<N<1001) piles of blocks where each pile has N_i (between 0 and 1000 inclusive) blocks. Find the largest rectangle in the blocks.

Eg:

3 4 4 5 3
      *
  * * *
* * * * *
* * * * *
* * * * *

The largest rectangle is 15 blocks (5 wide by 3 high).

Another Eg:

2 4 4 6 1
      *
      *
  * * * 
  * * *
* * * *
* * * * *

The largest rectangle is 12 blocks (3 wide by 4 high)

I tried a brute force approach, using all possible slices, but it was to slow because there are N^N slices.
NOTE: Only the largest rectangle needs to be outputted its dimensions are irrelevant.
Also, if anyone needs me to explain something more clearly please ask.

[koppaka]

can the input (Ni that is the no of piles in each block)be given in ascending order?

[koppaka]

if the condition is that the input must be random then do the following:
1.take the input into an array of size N(no of blocks)
2.sort the array by using merge sort.
3.then multiply every element in the array with the no of elements after the element in the array including the element(which means we are multiplying every element with the no of elements which are greater than and equal to the element in the array)
eg:
consider an ith element in the array .
multiply the ith element with (n-(i+1)).

let the array be 3,5,8,9
3*4(3=element;4=no.of elements greater than and equal to 3)
5*3
8*2
9*1

4.then find the maximum no which will the largest rectangle.
for eg:
in the above eg,out of
3*4
5*3
8*2
9*1
the maximum no is 8*2=16
so for the largest rectangle is 16 blocks(8 high and 2 wide)

[Disch]

The largest rectangle that uses all of pile P will extend through all piles which have heights >= the height of P.

Using this, you can form 'N' rectangles (where N is the number of piles), each rectangle has a height of height(P) and extends as far right as possible.

You then take the biggest rectangle of that subset.

Example:

2 4 4 6 1
      *
      *
  * * * 
  * * *
* * * *
* * * * *

P=0: height=2, extends to P=3 (inclusive). Size=8
- current best = 8
P=1: height=4, extends to P=3. Size = 12
- current best = 12
P=2: height=4, extends to P=3. Size = 8
- current best = 12
P=3: height=6, extends to P=3. Size = 6
- best = 12
P=4: height=1, extends to P=4. Size = 1
- best = 12


Solution is 12.



EDIT: actually this wouldn't quite work as shown by extending right only. You'd have to extend left AND right.

Also, as an optimization, you can skip piles where height(P) == height(P-1)

[Script Coder]

koppaka wrote:

can the input (Ni that is the no of piles in each block)be given in ascending order?

No sorting is not allowed. You have to use the piles as is.

Disch wrote:

The largest rectangle that uses all of pile P will extend through all piles which have heights >= the height of P.

That could be a solution. Although would the worst case not be n^n?

[Disch]

Worse case would be N*N which would happen if all piles have equal heights.

But if you do that optimization I talked about (skipping P when its height is equal to height of P-1), then that actually becomes the best case. N+N


Though my understanding of big O notation is limited and I might have it slightly wrong. There's no way this would be N^N though.

[Script Coder]

There's no way this would be N^N though.

Yes, you are right. Sorry It would be N(N-1) thus: N*N.
My gut is telling me that there is possibly a linear solution.

[Disch]

I don't see how. The logic demands that the height of the best rectangle is dependent on the heights of several adjacent rows.

You could do one pass of the piles and keep track of all possible running rectangles, but that still wouldn't be O(N), it would be O(N*Ni) and would be a lot more complex to write.

[Script Coder]

True, thanks for all the help, I think I have a clear direction in which to go.