The latest Ruby Quiz asks us to
find the maximum contiguous subarray, given an array.
This ties in nicely to something I've been wanting to ask for a while: how do you design your algorithms?
What heuristics do you use? What different approaches do you try? How can you improve your skill set
at designing algorithms?
For the maximum subarray problem, if you didn't know any better, you'd probably implement a solution that
analyzes every possible subarray, and returns the one with the maximum sum:
class Array
def sum
result = 0
self.each do |i|
result+=i
end
return result
end
#test every sub array - brute force!
def max_sub_array_order_ncubed
left_index = 0
right_index = 0
max_value = self[left_index..right_index].sum
for i in (0..self.length)
for j in (i..self.length)
this_value = self[i..j].sum
if (this_value > max_value)
max_value = this_value
left_index=i
right_index=j
end
end
end
return self[left_index..right_index]
end
end
If you were a bit more clever, you might notice that
self[i..j].sum is equal to
self[i..(j-1)].sum + self[j] in the innermost loop (the
sum method itself), and use an accumulator there as opposed
to calculating it each time. That takes you down from n
3 to n
2 time.
But there are (at least) two other ways to solve this problem:
-
A divide and conquer approach that uses recursion and calculates the left
and right maximum contiguous subarrays (MCS), along with the MCS that contains the right-most
element in the left side and the left-most element in the right side. It compares the three
and returns the one with the maximum sum. This gets us to O(n log n) time.
-
An approach I'll call "expanding sliding window." If memory serves me correct, this
aptly describes it or was the way a professor of mine described it.
In any case, the "expanding sliding window"
can do it in one pass (O(n) time), at the cost of a few more variables.
Clearly, these last two approaches aren't nearly as obvious as the first two - so how do you devise them?
I'm fairly confident that the only reason I know about them is from a course in algorithms where they
were presented to me (and I didn't take the time to work-through and reimplement them for this post).
I'm not sure that
TDD or just a long ponder
would have led me in that direction.
(Although, one of the solution submitters claims he TDDed the O(n) solution.)
Three thoughts in designing algorithms I use off the top of my head are:
- There's always brute force, but is there something better?
- Is divide and conquer and option? If so, is it easy enough to implement and understand?
- How can I trade space complexity for gains in time complexity, or vice versa if the situation warrants? (overview on computational complexity)
My assumption here is that you're not looking for someone else's code that has implemented it,
or that no one has already solved it. Of course in real work you'd probably want to look for an algorithm
that had already been discovered and published that provides a solution.
Is it just a matter of reading
Knuth's
compendium and books on algorithms, becoming familiar with many different types of them for many different data structures?
So I'll ask again: how do you design your algorithms? What heuristics do you use?
What different approaches do you try? How can you improve your skill set at designing algorithms?
What other questions do you ask yourself?
Hey! Why don't you make your life easier and subscribe to the full post
or short blurb RSS feed? I'm so confident you'll love my smelly pasta plate
wisdom that I'm offering a no-strings-attached, lifetime money back guarantee!
Leave a comment
Can u pls explain me ? I could not understand the sum function
Posted by Ganesh
on Feb 25, 2012 at 07:48 PM UTC - 5 hrs
Leave a comment
