Maximum subvector problem

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:

Maximum subvector problem

Bye