99% of Sup Forums can't solve this

99% of Sup Forums can't solve this

Attached: maxRectInHistogram.png (735x442, 12K)

Other urls found in this thread:

geeksforgeeks.org/largest-rectangle-under-histogram/
prismoskills.appspot.com/lessons/Arrays/Largest_rectangle_under_histogram.jsp
stackoverflow.com/editing-help
twitter.com/NSFWRedditImage

do your own homework jamal

function maxRectInHistogram(histogram) {
return Math.max(...Array(Math.max(...histogram)).fill(0).map(function (_, row) {
var counter = 0;
return Math.max(...histogram.map(function (value) {
counter = (value >= row) ? counter + 1 : 0;
return counter;
}).map(value => value * row));
}));
}


Just checking if you fuckers can get on my level.

That's just bruteforcing it.
Anyone can do that.

code g0re

it's not though

its 13 not 12

4 x 3 = 13
Sup Forums has spoken

Looks like that's 5x1.

What the fuck are they doing, combining rectangles separated by white space?

Give me a real world use case where you'd need to do this

lossy compression

lossless actually

public int largestRectangleArea(int[] height) {
Stack left = new Stack();
int cur = 0, area = 0;
while (cur < height.length) {
if (left.isEmpty() || height[cur] >= height[left.peek()]) {
left.push(cur++);
} else {
int top = left.pop();
area = Math.max(area, height[top]*(left.isEmpty() ? cur : (cur-left.peek()-1)));
}
}
while (!left.isEmpty()) {
int top = left.pop();
area = Math.max(area, height[top]*(left.isEmpty() ? cur : (cur-left.peek()-1)));
}
return area;
}


you're the 99%

int main(){
return 12;
}
;)

Ops, wrong cell.
a = [1,0,1,3,2,4,5,4,1,2,0]
sol = [0] * (max(a) + 1)
max_region = 0

for i in a:
x = list(range(i+1)) + [0] * (max(a) + 1 - i)
sol = list(map(lambda x,y: (x+y if y>0 else 0), sol, x))
max_region = max(max_region, max(sol))
print(max_region)

Mine's a much more primitive version of this

def maxArea(histogram):
maxA = 0
for index, startCol in enumerate(histogram):
for height in range(startCol, 0, -1):
width = 0
for endCol in histogram[index:]:
if endCol >= height:
width += 1
else:
break
maxA = max((maxA, width * height))
return maxA

geeksforgeeks.org/largest-rectangle-under-histogram/
ez

Attached: Screenshot from 2018-03-21 09-06-22.png (609x602, 43K)

I bet this doesn't work.

Looks good, and O(n), too. Garbage readability.

>javascript

Made it so it works on floats.

Attached: Screenshot from 2018-03-21 09-20-22.png (740x680, 48K)

Spent exactly 1 hour on this shit. Pretty sure it can be done better for some corner cases, here it is:
EDIT: fucked up my [CODE] tags
(def test1 [1 0 1 3 2 4 5 4 1 2 0])
(def test2 [1 0 1 0 3 0 1 255 10000000 1 2 4 0 5 4 1 2])
(def test3 [1 0 1 0 3 0 1 255 10 1 2 4 0 5 4 1 2])
(def test4 [1 0 1 0 3 0 1 255 509 1 2 4 0 5 4 1 2])


(defn slicer [seq']
(let [threshold (apply min seq')
eq? #(= threshold %)]
(some->> seq'
(partition-by eq?)
(remove #(eq? (first %))))))

(defn opisafag
([hs] (benis hs 0))
([hs maxarea]
(let [localmin (apply min hs)
localmax (apply max hs)]
(if (= 2 (count hs))
(max maxarea localmax (* 2 localmin))
(apply max
(* localmin (count hs))
(flatten
(for [z (slicer hs)]
(opisafag z maxarea))))))))

(opisafag test1)
(opisafag test2)
(opisafag test3)
(opisafag test4)

EDIT2: forgot the fucking return values
(opisafag test1)
=> 12
(opisafag test2)
=> 10000000
(opisafag test3)
=> 255
(opisafag test4)
=> 510

>O(n^2 ) solutions
Garbage

All of the solutions here are O(n!!!!!!)

> faggot who can't into computational complexity

mine is O(n*log(n)), suck a dick

This is O(n^2). There's a map and range function both of which are O(n) inside a O(n) for cycle.

THIS IS NOT FUCKING DOABLE!!!

> t. brainlet

what about it?

Okay last submission it's now parallelized and I threw in a benchmark.

Attached: Screenshot from 2018-03-21 10-09-52.png (678x549, 43K)

Still no O(N) solution? Fucking brainlets.

>Output 12
This bothers me, 5 is highest number so it has to be multiple of that, yet it's not. what the fuck.

Attached: 700-18807-RETARD+AWARD.jpg (700x460, 210K)

so what would be the result for [2,2,3,3,1] ?
6 -> [3,3] or
8 -> [2,2,3,3] ? There's a rectangle here

Bigger area wins. So 8 is output.

8 as you've said

It can be done in O(n).

...

two stoopid to do better than O(n^2)
#include
#include
#include

int
max_rect(size_t *hist, size_t len)
{
int cur, max = -1;
size_t i, j;
for (i=0; i max)
max = cur;
}
return max;
}

int
main(void)
{
size_t len, i;
size_t *hist;
if (scanf("%ld", &len) != 1)
err(1, "scanf");
if ((hist = malloc(sizeof(size_t) * len)) == NULL)
err(1, "malloc");
for (i=0; i

This can be solved worst case log n.

left = [(-1,-1)]
output = 0
for w, h in enumerate(input + [-1]):
while h < left[-1][1]:
lw, lh = left.pop()
output = max(output, lh * (w - lw))
left.append((w, h))
print(output)

Kek, would love to know how'd you come to that conclusion.

Magic data compression that makes his data size O(log n).

typedef struct stack stack;

int leftArray[11] = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0};
int rightArray[11] = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0};
int input[11] = {1, 0, 1, 3, 2, 4, 5, 4, 1, 0, 2};
int length = 11;

stack *s = NULL;

struct stack {
stack *next;
int v;
};

int isEmpty()
{
if(s == NULL) return 1;
return 0;
}

int peek()
{
return s->v;
}

int pop()
{
int n = s->v;
stack *temp = s->next;
free(s);
s = NULL;
s = temp;
return n;
}

void push(int v)
{
if(s == NULL)
{
s = malloc(sizeof(stack) * 1);
s->v = v;
s->next = NULL;
return;
}
stack *temp = malloc(sizeof(stack) * 1);
temp->v = v;
temp->next = s;
s = temp;
}

void solve(){
int i, maxL = 0;
for(i = 0; i < 11; ++i) //left to right
{
if(!isEmpty() && input[i] < peek())
{
++maxL;
leftArray[i] = maxL;
pop();
}
else
{
leftArray[i] = maxL;
push(input[i]);
maxL = 0;
}
}
freeStack();
maxL = 0;
for(i = length; i >= 0; --i) //right to left
{
if(!isEmpty() && input[i] < peek())
{
++maxL;
rightArray[i] = maxL;
pop();
}
else
{
rightArray[i] = maxL;
push(input[i]);
maxL = 0;
}
}
freeStack();
int max = 0;
for(i = 0; i < length; ++i)
{
int n = input[i] + leftArray[i] * input[i] + rightArray[i] * input[i];
if(n > max) max = n;
}
printf("%d\n", max);
}

>geeksforgeeks.org
dang it pajeetpuzzle.org never explains why shit works, or how to generalize it. Fucking rote learners.
Now I need to spend time actually making a mental effort, maybe even getting a pen and paper out to properly grok it. And I'm way too lazy for that shit rn.
And I'm too lazy to even jewgle a non-pajeet explanation

>everything else uses hardcoded N
>stack is linked list for no good reason
>language is so shit that 75% of his code is basic data struct implementation
So this is the power of Cee.

Attached: blub.png (454x281, 69K)

def hist(x):
result = 0
for i in range(len(x)-1):
multiplier = 1
current = x[i]
try:
while x[i+1] >= current:
multiplier += 1
i += 1
area = current * multiplier
except:
pass
if area > result:
result = area
return result
shitty solution I pooped out in 10 minutes, I'll come back later with an optimized version.

beginner c

You are right
here, redid my solution so it's O(n), took me ~15 mins tops
(def test1 [1 0 1 3 2 4 5 4 1 2 0])
(def test2 [1 0 1 0 3 0 1 255 10000000 1 2 4 0 5 4 1 2])
(def test3 [1 0 1 0 3 0 1 255 10 1 2 4 0 5 4 1 2])
(def test4 [1 0 1 0 3 0 1 255 509 1 2 4 0 5 4 1 2])

(defn opisamassivefag [hs]
(let [testcase (vec hs)]
(reduce-kv (fn [maxarea idx itm]
(some->> idx
(subvec testcase)
(take-while #(>= % itm))
count
(* itm)
(max maxarea)))
0
testcase)))
; tests:
(opisamassivefag test1)
=> 12
(opisamassivefag test2)
=> 10000000
(opisamassivefag test3)
=> 255
(opisamassivefag test4)
=> 510

include .youreyes
init youreyes

if(n -> rectangle)
{
do for (log n^2) { i++; }
}
print(ctrl);

import histogramRectangle

def solve(hist):
return HistogramSolver(hist).solve()

prismoskills.appspot.com/lessons/Arrays/Largest_rectangle_under_histogram.jsp

Here, supplementary "explanation" for you. Feel free to drop your brain or something.

Also, OP's solution sucks:
maxRectInHistogram([1, 0, 1, 3, 2, 4, 5, 4, 1, 2, 0])
12

maxRectInHistogram([1, 0, 1, 3, 2, 255, 10000000, 1, 2, 4, 0, 5, 4, 1, 2])
RangeError: too many function arguments debugger eval code:2:24
//>imblying javasgribd

maxRectInHistogram([1, 0, 1, 3, 2, 255, 10, 1, 2, 4, 0, 5, 4, 1, 2])
254
//wtf? 255*1=254 according to OP?

maxRectInHistogram([1, 0, 1, 3, 2, 255, 509, 1, 2, 4, 0, 5, 4, 1, 2])
510

i'd post my solution but i don't know how to do code blocks on here

Attached: bl.png (645x729, 77K)

Here's a guide: stackoverflow.com/editing-help

>stackoverflow.com/editing-help

penis
test
penis

you tricked me

Attached: ..jpg (569x336, 35K)

Math and programming brainlet here. Pretty hyped, I think I did it (c#). Also the variable name 'rectangle' is misleading but I couldnt think of a better name for the time being

public int CalculateLargestArea(int[] histogram)
{
int maxArea = 0;

for (int i = 0; i < histogram.Length; i++)
{
//Create a new list; add the current column to it
List rectangle = new List();
rectangle.Add(histogram[i]);

//Check if left column(s) valid
for (int j = i-1; j >= 0; j--)
{
if (histogram[j] >= histogram[i])
{
rectangle.Add(histogram[j]);
}
else break;
}

//Check if right column(s) valid
for (int k = i+1; k = histogram[i])
{
rectangle.Add(histogram[k]);
}
else break;
}

//Calculate biggest possible area based on current combination
int area = rectangle.Count * rectangle.Min();

maxArea = (area > maxArea) ? area : maxArea;
}

Attached: itme.jpg (800x450, 41K)

oops, cut off the "return maxArea"

def getAreas(p):
for i, x in enumerate(p):
for ix, xx in enumerate(p[i::]):
if xx < x:
yield (ix-i)*x
print max(getAreas([1,0,1,3,2,4,5,4,1,2,0]))

Find max value and scan left and right to see if there's any other values equal or greater. If there are, keep adding to the current sum until you encounter a value which is less than your current max. The sum is the value for your new rectangle if it's greater than whatever value you had for the sum before. Find the next maximal value which is less than the max you just worked with and repeat until you hit 0.

Return whatever the sum is.

Heh, fantastic.

Nice.
But why does it give two values the second time?

If you didn't solve this with dynamic programming you're an Indian

no u

You don't need dynamic programming here, it's a single loop with a standard max search you overengineering monkey.

wrong for e.g. p=[3,2]

def getAreas(p):
for i, x in enumerate(p):
for ix, xx in enumerate(p[i::]):
if xx < x:
yield ix*x
break
print list(getAreas([0,0,1,7,2,0,0,0,0,2,0]))

ftfy

Attached: torv.jpg (481x640, 52K)

Hello pajeet my sir
please run your algorithm on this:
[2,3,2]

haha how long did that take you

Attached: 2f7[1].jpg (601x508, 28K)

def largest_rect_in_histogram(hist):
rect = 0
for i in range(1, max(hist)+1):
tmp = 0
for j in hist + [0]:
if j >= i:
tmp += i
else:
if tmp > rect:
rect = tmp
tmp = 0
return rect

awful feet

Where can I find more of these?Just starting to learn haskell and these math heavy problems are perfect training material. Image search doesnt get me far.

google 'coding job interview questions'

int func(){
return 12;
}

The absolute state of Sup Forums.
Full of brainlets and code pajeets.

Attached: fucking_disgusting_bitch.jpg (640x480, 49K)

rectogram = (hi) => Math.max(...new Array(Math.max(...hi)).fill(hi).map((a,i) => Math.max(...hi.map(e => (e>=i)*1).join('').split('0').map(e => e.length))*i))

rectogram([1,0,1,3,2,4,5,4,1,2,0])
>12


not that I expect anyone to get this..

Do your homework yourself.
It's piss easy and you should be ashamed to seek help for it.

> jabbasgribd
learn a real programming language
rectogram([1,0,1,3,2,255,500000,4,1,2,0])
499999

what >>>real

C? I mean look at the OS

>rectogram([1,1,1,1,1,1,1])
>0

>rectogram([0,0])
>-Infinity

OK.

This is incorrect. You also need to loop backwards

>0.0002% error is acceptable imo
also this: The absolute state of the webdev codemonkeys.

let f = h => h.reduce((m,t) => Math.max(m, t*Math.max(...h.map(a=>a>=t?1:0).join('').split('0').map(a=>a.length))), 0)

> f([1,0,1,3,2,4,5,4,1,2,0])
12
> f([1,0,1,3,2,255,500000,4,1,2,0])
500000
> f([1,1])
2
> f([0,0])
0

const find = list => {
let maxArea = 0;
const ranges = Array.from({length: list.length}).map((_, i) => i +1);
for (const width of ranges) {
for(let index of list) {
index = parseInt(index, 10);
const currentList = [...list,...list].splice(index, width)
const smallest = currentList.reduce(
(total, current) => current < total ? current : total,
Infinity
)
const potential = smallest * width;
if (potential > maxArea){
maxArea = potential
}
}
}
return maxArea
}

console.log(find([1, 0, 1, 3, 4, 5, 4, 1, 2, 0]))


That absolute quickest I could put together

import histogramBiggestRectangle

if __name__ == "__main__":
histogram_biggest_rectangle = histogramBiggestRectangle
histogram_biggest_rectangle.solve(histogram)

I am god

>Exploiting this property, following algorithm can be used
Still lrn2english tier text. Better than pajeetcentral.org tho.
Not enough pictures to understand this without making an effort tho, 2/10
Frankly, it is indeed a somewhat better piece of text than the pajeet version, owing to the occasional explanations of the underlying logic.

heh, I like you
made me crack a smile

>couldnt think of a better name for the time being
rekt (from rektangel, komrad)

My version, shitty but it werks
int max(int a, int b) { return a > b ? a : b; }
int min(int a, int b) { return a < b ? a : b; }

int getFurthestItemInHistogram(int *histogram, int histogramSize, int columnSize, int startIndex, int direction)
{
int i = startIndex;
for(; i >= 0 && i < histogramSize; i += direction)
{
if(histogram[i] < columnSize)
return i - direction;
}
return max(0, min(i, histogramSize - 1));
}

int getLargestArea(int *histogram, int histogramSize)
{
int largestArea = 0;
for(int i = 0; i < histogramSize; i++)
{
int columnSize = histogram[i];
int itemLeft = getFurthestItemInHistogram(histogram, histogramSize, columnSize, i, -1);
int itemRight = getFurthestItemInHistogram(histogram, histogramSize, columnSize, i, 1);
int area = (1 + itemRight - itemLeft) * columnSize;
largestArea = max(area, largestArea);
}
return largestArea;
}

Cracking the Coding Interview (book),
leetcode (website)

Homework

$ ./grect

>./grect
>not ./getrekt