### Thread: Maximum segment sum: language comparison

1. No Profile Picture
Contributing User
Devshed Novice (500 - 999 posts)

Join Date
Nov 2002
Posts
596
Rep Power
24

#### Maximum segment sum: language comparison

I am reading Introduction to Functional Programming with Haskell (http://web.comlab.ox.ac.uk/oucl/publications/books/functional/) and was very impressed by the elegance of the solution to the maximum segment sum. The mss of the sequence
Code:
`[-1, 2, -3, 5, -2, 1, 3, -2, -2, -3, 6]`
is 7, the sum of [5, -2, 1, 3]

Bird's rather awesome solution to this is
Code:
```mss = maxlist . scanr (maxZero) 0
where maxZero x y = 0 `max` (x + y)
maxlist = foldr1 (max)```
(Edit - apols, can't get indetation right on haskell code...)
This manages to be at once dense and not at all unreadable, even for someone learning the language...and I wondered what it would look like in other languages.

What would this look like in your favourite language? Bring me your scheme, your assembler, your perl! :-) Java lovers win kudos for daring to show their face :-)

The only one I've tried so far is python. I thought it would be pretty concise too, as lists are home turf and there is some support for higher order funtions, but I was surprised in the end at how may hoops I had to jump through. Python doesn't have anything like scanr and in the book Bird begins with a more easily understandable version
Code:
```mss = maxlist . map sum . segs
where segs = concat . map inits . tails```
so I decided to start there, recreating the haskell builtins concat (flatten a list one level), init (return all initial segments of a list) and tails (return all final segments of a list). I also needed to work around the fact that in python list.extend returns None, which is broken IMHO:
python Code:
```
from operator import add
def mss(lst):
if len(lst) == 0:
return 0
segs = getSegs(lst)
return reduce(max, map ((lambda x: reduce(add, x)), segs))

def getSegs(lst):
return concat(map((lambda x: inits(x, 0)), tails(lst)))

def myExtend(lst, val):
lst.extend(val)
return lst

def tails(lst):
if len(lst) == 0:
return []
return myExtend([lst], tails(lst[1:]))

def inits(lst, count):
if count > len(lst):
return []
return myExtend([lst[0:count]], inits(lst, (count + 1)))

def concat(lst):
"""flatten 1 level and remove empty lists, because python's map won't deal nicely with them."""
lst2 = []
for l in lst:
for m in l:
if m != []:
lst2.append(m)
return lst2```

So 1 Nil to haskell, and not only because of the builtins. I am no pythonista and hope that someone will prove me wrong with a better version than this.

Disclaimer: this problem is ideal for a language like haskell, because it specialises in recursion over structures and the point-free and functional composition styles (omitting params from function definitions and syntax like f . g) make it possible to express this all very cleanly.
Last edited by jamieB; June 10th, 2006 at 02:23 AM. Reason: fixing python function mss
2. No Profile Picture
Contributing User
Devshed Intermediate (1500 - 1999 posts)

Join Date
Feb 2004
Location
London, England
Posts
1,585
Rep Power
1374
The algorithm you give looks massively complex and slow - it is at least O(N^2), possibly more (I dont know enough haskell to say for sure).

There is a much simpler algorithm that is O(N). Here it is in python:

Code:
```>>> def mss(lst):
... 	maxSoFar = 0.0
... 	maxEndingHere = 0.0
... 	for val in lst:
... 	    maxEndingHere = max(maxEndingHere+val, 0.0)
... 	    maxSoFar = max(maxSoFar, maxEndingHere)
... 	return maxSoFar
...
>>> mss([-1, 2, -3, 5, -2, 1, 3, -2, -2, -3, 6])
7.0
>>> mss([31,-41,59,26,-53,58,97,-93,-23,84])
187.0```
This is adapted from the book Programming Pearls by Jon Bentley, which has a whole chapter on alternative algorithms for this problem.

Bentley goes on to give comparisons of the runtime for the algorithms for different size lists. The difference can be huge -for a large list the runtime for O(N^2) can be measured in months, while for O(N) it is in seconds.

Dave
3. No Profile Picture
Contributing User
Devshed Novice (500 - 999 posts)

Join Date
Nov 2002
Posts
596
Rep Power
24
Originally Posted by DevCoach
The algorithm you give looks massively complex and slow - it is at least O(N^2), possibly more (I dont know enough haskell to say for sure).

There is a much simpler algorithm that is O(N). Here it is in python:

Code:
```>>> def mss(lst):
... 	maxSoFar = 0.0
... 	maxEndingHere = 0.0
... 	for val in lst:
... 	    maxEndingHere = max(maxEndingHere+val, 0.0)
... 	    maxSoFar = max(maxSoFar, maxEndingHere)
... 	return maxSoFar
...
>>> mss([-1, 2, -3, 5, -2, 1, 3, -2, -2, -3, 6])
7.0
>>> mss([31,-41,59,26,-53,58,97,-93,-23,84])
187.0```
This is adapted from the book Programming Pearls by Jon Bentley, which has a whole chapter on alternative algorithms for this problem.

Bentley goes on to give comparisons of the runtime for the algorithms for different size lists. The difference can be huge -for a large list the runtime for O(N^2) can be measured in months, while for O(N) it is in seconds.

Dave
Thanks Dave, that certainly is simpler! I plan to read Bentley's book asap...

According to Bird the inefficient but easy to understand algorithm I transposed into python is O(n^3). There are about n^2 segments and summing them all takes n^3 steps. He refines this to end up with the first one I showed, which is linear-time like yours.
4. No Profile Picture
Contributing User
Devshed Intermediate (1500 - 1999 posts)

Join Date
Feb 2004
Location
San Francisco Bay
Posts
1,941
Rep Power
1314

#### Obligatory PostScript post :)

Here is DevCoach's algorithm in PostScript:
Code:
```/mss {
0 exch 0 exch {
add dup 0 lt {
pop 0
} if
2 copy lt {
exch pop dup
} if
} forall
pop
} def```
Code:
```GS> [-1 2 -3 5 -2 1 3 -2 -2 -3 6] mss ==
7
GS> [31 -41 59 26 -53 58 97 -93 -23 84] mss ==
187```

#### Comments on this post

• LinuxPenguin agrees : I think it's great you're using it a lot, since noone else is :)
5. Here's an admittedly somewhat clumsy version of the Bentley algorithm in Scheme:

Code:
```(define (max-segment x)
(let mss ((segment x)
(max-ending-here 0.0)
(max-so-far 0.0))
(let* ((next-segment (cdr segment))
(new-sum (max 0.0 (+ (car segment) max-ending-here)))
(new-max (max new-sum max-so-far)))
(if (null? next-segment)
new-max
(mss next-segment new-sum new-max)))))```
This just doesn't sit well with me, though; I'll try coding the first solution in Scheme later.
Last edited by Schol-R-LEA; June 17th, 2006 at 02:38 AM.
6. No Profile Picture
Contributing User
Devshed Novice (500 - 999 posts)

Join Date
Nov 2002
Posts
596
Rep Power
24
Originally Posted by Schol-R-LEA
Here's an admittedly somewhat clumsy version of the Bentley algorithm in Scheme:

Code:
```(define (max-segment x)
(let mss ((segment x)
(max-ending-here 0.0)
(max-so-far 0.0))
(let* ((next-segment (cdr segment))
(new-sum (max 0.0 (+ (car segment) max-ending-here)))
(new-max (max new-sum max-so-far)))
(if (null? next-segment)
new-max
(mss next-segment new-sum new-max)))))```
This just doesn't sit well with me, though; I'll try coding the first solution in Scheme later.
scheme should be a good fit for Bird's algorithm...I'd be interested to see how close you can get to haskell's brevity and elegance.