2/18 To show I am a better man (and christian) than ilyas, here is a
solution to the hw question asked yesterday (maximum contiguous
sequence). Pass 1: coalesce adjacent elements of the array A
into blocks with the same sign (dropping 0) by summation into array B,
meanwhile keeping track of their range in array A . Finding the max
of the array B during this pass as well. Pass 2: starting at the
max block, extending up and down the array B (and hence A), finding
the max stretch. You have to prove that it works and it is linear. :)
\_ anti-semite alert!!!
\_ I don't think ilyas is Jewish
\_ No, he's either Tzimisce or Silverfang lupus theurge. Aren't
you paying attention? *sheesh*
\_ mislycanthropy alert?!
\_ Doesn't this give 4 instead of 5 for A = B = (4, -8, 3, -1, 3)?
\_ What's wrong with you dude? We solved this already in one pass.
Just stop already.
\_ Was it O(n) or O(n^2)?
\_ One pass, O(n). I don't see what's the big deal. Keep a
running count of the "current sequence", and the value/index
where it was highest. The "current sequence" is over if
(count + next) < next. Store the best sequence as you go.
\_ Except that doesn't work. -- ilyas
\_ Counterexample? You may call me stupid rather than lazy.
Although being anonymous helps me in either case.
\_ Think of one yourself. Lazy bitch. -- ilyas
\_ I choose to think I'm right and you're stupid.
\_ Let me know what you get on your homework.
-- ilyas
\_ cool! christians rule.
\_ Not only have you encouraged the deadly sin of Sloth in the original
poster of the question, but you have succumbed to the deadly sin of
Pride yourself (by posting something that doesn't work).
You -> Hell. It's trivial to see that starting from the max block
can fail to work. -- ilyas
\_ You just succumbed to the deadly sin of Stupidity for getting
trolled again.
\_ Nay, for ilyas knoweth not what he does. |
http://csua.com/feed/