Kadane's Algorithm in Scheme (Racket)

Question

I understand the logic behind how Kadane's Algorithm (maximum sum of all sequential sub-arrays in an array) works in "pseudo-code," and I'm sure I could implement it as a function in C or C++. However, I'm trying to implement it using lists in Scheme (Racket; the file extension is .rkt), which I have no experience with.

The end result I'm looking for is...

Input: (maxsum `(1 4 -2 1))
Output: 5

So far I've developed two helper functions I may be able to use within the maxsum function.

(1) size: returns the number of elements in a list.

(define size
   (lambda (list)
      (cond
         [(not (list? list)) 0]
         [(null? list) 0]
         [else (+ 1 (size (cdr list)))]
      )
   )
)

(2) sum: returns the sum of all elements in a list.

(define sum
   (lambda (list)
      (cond
         [(not (list? list)) 0]
         [(null? list) 0]
         [else (+ (car list) (sum (cdr list)))]
      )
   )
)

How would I go about defining/designing the maxsum function?

Answer 1

Here is a version patterned after the Phyton code on wikipedia:

(define (maxsum lst)
  (define (aux lst max-ending-here max-so-far)
    (if (null? lst)
        max-so-far
        (let ((new-max-ending-here (max 0 (+ (car lst) max-ending-here))))
          (aux (cdr lst) new-max-ending-here (max max-so-far new-max-ending-here)))))
  (aux lst 0 0))

(maxsum '(1 4 -2 1))   ; => 5

(maxsum '(-2 1 -3 4 -1 2 1 -5 4))  ; => 6

It is tail recursive, so it will be compiled into an efficient iterative program.