So folks,
again a life sign from me. Again I'm busy... Currently I'm writing the paper of my study thesis. This needs more time than I thought but fortunately my monitoring unit works on the fpga. On the side I started to learn for my last oral exam - in computer graphics. That means hard-core diving into bézier and b-spline curves, also in point clouds. That's gonna be difficult and time-consuming.
Nevertheless while surfing, I came across a paper about the so-called maximum subvector problem. I even think that I really had this problem some years ago while coding. Although it's quite simple it's somehow cool to think about solving it. So what it is about?
given : an array[1...n] of (positive and negativ) numeric values
goal: to determine the maximum subvector a[i..j], 1 <= i <= j <= n whose sum of elements is maximum over all subvectors. Well, not that big thing at first - just calculate all possible subvectors and save the maximum one. The straightforward approach could be look like this: MaxSoFar := 0.0
for L := 1 to N do
for U := L to N do
Sum := 0.0
for I := L to U do
Sum : = Sum + X[I]
/* Sum now contains the sum of X[L..U] */
MaxSoFar := max(MaxSoFar, Sum)
This works of course but for even quite small array sizes (e.g. 1000 elements) this lasts quite long. The execution time is proportional to O(n^3)!
This just be motivation enough to search for some better algorithm. Well, after some thinking you might find a O(n^2) algorithm. There is even a divide-and-conquer approach which is in O(nlogn), but it's not that easy to code :-( Ok, nice, they are often hard to implement...
But in fact there is a simple algorithm that works in linear time! Yes, in O(n)! I must admit I had never expected it nor searched for it. And it is so simple!!!
Curious? Ok here it is:
MaxSoFar := 0.0
MaxEndingHere := 0.0
for I := 1 to N do
MaxEndingHere := max(MaxEndingHere+X[I], 0.0)
MaxSoFar := max(MaxSoFar, MaxEndingHere)
So if you found this blog entry interesting, then be sure to check out following article, it contains everything I've written here:
Bye
Subscribe to:
Post Comments (Atom)
5 comments:
Nice fill someone in on and this mail helped me alot in my college assignement. Say thank you you for your information.
What a great resource!
Your blog keeps getting better and better! Your older articles are not as good as newer ones you have a lot more creativity and originality now. Keep it up!
And according to this article, I totally agree with your opinion, but only this time! :)
Correctly your article helped me altogether much in my college assignment. Hats off to you enter, choice look forward in the direction of more interdependent articles soon as its anecdote of my choice topic to read.
Really intelligent entry to read on.. I am truly compelled with this article. Looking forward for more info.
sialis dostavka po moskve
Post a Comment