Area calculation

[Encrypted]

Hi!

 

Let's say we have a bunch of numeric data.

 

Example:

3 1 5 4

 

Each of the numbers represents a vertical line containing exactly that many "squares" that have a certain measure. Each of the vertical lines' widths is exactly one square.

 

So, this means, that the first line is 3 squares in area, the second one 1, the 3rd 5 and the 4th 4.

 

Supposedly the lines are put together like this:

- - + -

- - + +

+ - + +

+ - + +

+ + + +

(Note: I do not have to draw the graph)

 

So, the problem I am trying to solve is, how to find the maximum area of a rectangle with this kind of data. In this case, it would be 8 squares:

- - + +

+ - + +

+ - + +

+ + + +

 

I've been trying to solve this problem for days, but am still kind of stumped. Is there a quick function to do this or do I have to make one up myself? If the latter is the case, how would it be best to do this?

 

Thank you in advance!

[thepip3r]

simple i believe...

 

if all of the squares are the same dimensions... we'll say 2x2, then your calc would be:

 

x * (L * H)

 

where x is the number of squares... so in ur example where you have a total of 13 squares, then the calc would be

 

13 * (2 x 2) = 52

 

Edit:

 

so in your last example, using my L and W calcs,

 

your equation would simply be:  8 * (2 * 2)

 

however, if, like you say, the square is a 1 x 1 square.. that's even easier...

 

your area would be 8 * (1 * 1) = which is obviously 8

[Encrypted]

Hmm, actually no.

 

I don't have to find the area of all the squares together. I need to find the size of the largest possible rectangle, just like the graph in my first post shows. The red area is the part I need the area for. The main problem is how to find the amount of squares in the largest possible rectangle, the rest is easy as pi(e).

 

The data is always different. That's why I need to build a program. So, the functions should be as algebraic as possible..

 

Edit: I just noticed the first post's last graph with the colored pluses doesn't contain the top line. Please note that it is in the graph above that and that the plus in the top line is still black.

[thepip3r]

lol ok.. well then ur not explaining it well.  but that should be easy as well.

 

if you want to find the largest pair of numbers (assuming that's your criteria for defining a rectangle), then simply add each number in it's occurring order into an array.  Then loop through the array until u find pairs of equal numbers.  when u find a pair, add those values to another array or a variable.  with each loop, if the next set of numbers is "larger" than the first, replace it... your resulting values would be the "largest possible rectangle" then calc the area off of that:

 

$array = array(3, 1, 5, 4, 4, 3, 2, 2, 1, 6, 5, 7, 3, 2, 6, 6, 2, 1, 1, 9);

$biggestNum = 0;
for ($i = 0; $size = sizeof($array); $i < $size; $i++) {
  if ($array[$i] == $array[$i + 1]) { $biggestNum = $array[$i]; }
}

$area = ($biggestNum * 2) * (L*W);

[Encrypted]

Well, yeah, as it seems, I have difficulties in explaining things in English. Sorry about that.

 

By "largest possible rectangle" I meant the largest rectangle by area.

 

So, with

$array = array(3, 5, 3, 1, 7);

the area would be 3*3 = 9 from the first 3 elements of the array.

 

Edit: I thought of looping it and finding out all different areas, which are interpreted as rectangles, but it would take forever if you have several thousands of vertical lines with their vertical length being maximally 100. I was wondering, if it is possible to develop a quicker solution for this kind of a problem and if is, then what do you suggest me to do?

[thepip3r]

in your most recent example, can you explain how you're getting 3*3?  for the array you referenced, i see 3, 5, 3, 1, 7.  do the numbers need to be the same?  meaning they are the same vertical length which would equal a rectangle?  ...that's what i assumed from my previous post.  for the array you mentioned, 3, 5, 3, 1, 7, each of those numbers represent a vertical line correct?  and if so... do they in themselves constitute a rectangle or does only a line of equal length adjacent to it constitute a rectangle?  i guess what i'm ultimately missing is what constitutes a rectangle?  I can't see how a vertical line with 3 boxes and a vertical line with 5 boxes would constitute a rectangle.  but i'm sure i'm interpreting that wrong.  please clarify and i'll see if i can't actually help you out instead of just cause confusion.  =P

[Encrypted]

Well, the graph would look like this:

O O O O +

O O O O +

O + O O +

O + O O +

+ + + O +

+ + + O +

+ + + + +

The "+" means a square and the "O" means empty area.

 

Basically, the red area is the rectangle. It's kind of hard to explain it so that everyone else would understand it, but I believe the graph explains it well enough.

 

That is the largest rectangle by area possible with this kind of data. It doesn't matter that one of the lines is valued 5, it still contains the 3 at the bottom necessary to construct that rectangle.