2/17 Quiz: What is an optimal algorithm for finding a contiguous sequence
in an array that when added will yield the greatest sum, where the
array contains both positive and negative numbers?
\_ -5 1 -2 8 -5 1 -1 100 -3 where the greatest sequence is
8-5+1-1+100
\_ Do you mean the greatest sequence of five numbers?
The greatest sequence is just all the positive numbers
if I understand your concept of "sequence"
correctly.
\_ The numbers must be adjacent, and the length of the
sequence is arbitrary. -!op
\_ The algorithm to solve this is still linear time.
Email me if you want the solution. Hint:
partition the array into 3 sums. -- ilyas
I ask again, do you partition the array into lumps of -/
positive and negative blocks, and go from there? Mine I think
works but requires you to do so first.
\_ No. I ask that you email me for a complete solution, because
I want to make sure this isn't homework. -- ilyas
\_ This is trivially linear time. -- ilyas
\_ No it's not. Assuming you're looking for the contiguous subset
of the input which has the largest sum, there are around N*N/2
possibilities, and a simple 2-pass linear search is not
gauranteed to find the right answer.
\_ does your algorithm first repartition the array into a sequence
of alternating positive and negative integers?
\_ Look, maybe you didnt state your problem correctly, but as
stated, the problem is easily solved by going through the array
once, and putting all positive numbers into the sequence.
-- ilyas
\_ don't be a moron, obviously he means a contiguous sequence
in the original array. -tom
\_ Maybe he meant 'greatest increasing subsequence.'
Sequences have nothing to do with adjacency.
Obviously indeed. You seem really smart, tom. -- ilyas
\_ It *is* obvious that op is not asking "what is
the set of numbers which adds up to the greatest
sum, given a set of positive and negative numbers"?
You seem really stupid, ilyas. -tom
\_ That much is clear from my reply: 'you probably
didn't state the problem correctly', etc. What
you seem to be missing is that there are multiple
interesting problems he may in fact be asking that
all involve arrays and sequences. I am not sure
why I am wasting my time explaining this to you.
-- ilyas
\_ Wow, I didn't realize you meant that in
"This is trivially linear time" -!tom
\_ -5 1 -2 8 -5 1 -1 100 -3 where the greatest sequence is
8-5+1-1+100
\_ Do you mean the greatest sequence of five numbers?
The greatest sequence is just all the positive numbers
if I understand your concept of "sequence"
correctly.
\_ The numbers must be adjacent, and the length of the
sequence is arbitrary. -!op
\_ The algorithm to solve this is still linear time.
Email me if you want the solution. Hint:
partition the array into 3 sums. -- ilyas
\_ Add all the positive numbers in the array and return that.
In other words, maybe you want to define sequence, or give us
more information.
\_ What is the optimal algorithm for finding the hottest, best match
for a long-term monogamous heterosexual relationship?
\_ Not sure this is right. But take a running total. Mark the array
index when the total is the lowest. Mark the array index when the
total is the highest. The sequence starts with the number after
the first array index, and ends with the number at the second array
index.
\_ This greedy algorithm fails. -- ilyas
\_ Usually you provide an example.
\_ For instance what happens when the lowest cumulative sum
is after the highest cumulative sum? If you constrain the
former to appear before the latter, it's not a global
max/min anymore, etc. Lazy bitch. -- ilyas
\_ Let's add one more feature. Track the highest single
positive value. If the highest single positive value
is greater than the sum of the sequence, then the
final answer is just the single value.
"Lazy bitch"? Dude, what's wrong with you?
\_ This still doesn't work. You didn't address the
problem of min occuring after max. -- ilyas
\_ Yeah. I was a little eager to post originally.
Sigh ... but if the global minimum running
total occurred befored the global maximum running
total, I'd be schweet. Again, though:
"Lazy bitch"? Dude, what's wrong with you?
\_ It's the price you pay for not thinking of a
counterexample yourself. Lazy bitch. -- ilyas
\_ Dude, you need to stop with the anti-social
behavior.
\_ And you need to stop being lazy. We
all could use improvement. I thought
I was being eminently reasonable in both
providing the requested counterexample,
and gently chiding the sin of sloth,
which, as our Christian friends will tell
us, is deadly. -- ilyas
\_ You must play a Silverfang. Probably a
a theurge, I'd guess. Nowhere else
would you see a combination of cryptic
utterances, arrogant stubbornnes,
and haughty condescending
intellectualism all wrapped around a
core of inflexible superiority bound
together by a completely unapologetic
nigh impregnable psyche. Bravo -- I'm
impressed. Now, the question is, are
you this way in real life, or are you
just giving motd a non-stop
demonstration of your rp abilities?
I'd guess the latter, but I'm sure
there are motd denizens that would
disagree with me. --!pp
\_ Paolo says I am Tzimisce. -- ilyas
\_ In this context, that's quite
a compliment -- though perhaps
somewhat backhanded iir all the
details....
\_ Seems like you can just keep a running count. If your next number is
bigger than your count would be by adding it, then you remember your
previous sequence if it's the biggest so far and start a new one.
You'd also have to keep the high point of the current sequence.
\_ Okay, I think this works. It's a two-pass solution.
Pass 1: Take the running total solution. Find the array index
where the minimum running total occurs. Find the index for the
max running total. If the min occurs before max, the sequence is
between the two.
Pass 2: If the min occurs after the max, then find the index of
the max after the min. The sequence will occur between the min
and and the new max.
Edge cases should be straightforward.
\_ This doesn't work either. The point of 170 homework is that
you prove the thing works. -- ilyas |
http://csua.com/feed/