We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
So max is 12... but wait, 3 forms the min height of a rectangle starting at 1 and ending at 5 for a total size of 15!
My suggestion is that you check if your previous index (j) skips (has a greater than one difference with the current) and if list[j] is less than our current value (if not, the regular algorithm will take care of it).
Largest Rectangle
You are viewing a single comment's thread. Return to all comments →
*edited I think I found a problem with Tushar Roy's algorithm.
I think this is a telling case: If you have this list (no delimiter) 24534513
list: 24534513 stack:012 i = 3 (push till a decreasing value found)
list: 24534513 stack:012 i=3 (i-p)*list[p] -> (3-2)5 -> (3-1)4 So we update max to 5 then 8, but 2<3 (list[0]
list: 24534513 stack:0 345 i=6 (push until decreasing again)
list: 24534513 stack:0 345 i=6 -> (1)5 -> (2)4 -> (3)3 -> (6)2
So max is 12... but wait, 3 forms the min height of a rectangle starting at 1 and ending at 5 for a total size of 15!
My suggestion is that you check if your previous index (j) skips (has a greater than one difference with the current) and if list[j] is less than our current value (if not, the regular algorithm will take care of it).