; maximum sum subsequence

(define (max-sum-subseq-1 xv)
  (let ((n (vector-length xv)) (max-so-far 0))
    (do ((i 0 (+ i 1))) ((= i n) max-so-far)
      (do ((j i (+ j 1))) ((= j n))
        (let ((sum 0))
          (do ((k i (+ k 1))) ((< j k))
            (set! sum (+ sum (vector-ref xv k))))
          (set! max-so-far (max max-so-far sum)))))))

(define (max-sum-subseq-2a xv)
  (let ((n (vector-length xv)) (max-so-far 0))
    (do ((i 0 (+ i 1))) ((= i n) max-so-far)
      (let ((sum 0))
        (do ((j i (+ j 1))) ((= j n))
          (set! sum (+ sum (vector-ref xv j)))
          (set! max-so-far (max max-so-far sum)))))))

(define (max-sum-subseq-2b xv)
  (define (cumarr x) (+ x 1))
  (let* ((n (vector-length xv))
         (real-array (make-vector (+ n 1) 0)))
    (vector-set! real-array (cumarr -1) 0)
    (do ((i 0 (+ i 1))) ((= i n))
      (vector-set! real-array (cumarr i)
        (+ (vector-ref real-array (cumarr (- i 1)))
           (vector-ref xv i))))
    (let ((max-so-far 0))
      (do ((i 0 (+ i 1))) ((= i n) max-so-far)
        (do ((j i (+ j 1))) ((= j n))
          (let ((sum (- (vector-ref real-array (cumarr j))
                        (vector-ref real-array (cumarr i)))))
            (set! max-so-far (max max-so-far sum))))))))

(define (max-sum-subseq-3 xv)
  (let-syntax ((x (syntax-rules ()
                    ((x i) (vector-ref xv i)))))
    (let maxsum3 ((l 0) (u (- (vector-length xv) 1)))
      (cond ((> l u) 0) ((= l u) (max 0 (x l)))
      (else (let ((m (quotient (+ l u) 2)))
              (let ((lmax 0) (sum 0))
                (do ((i m (- i 1))) ((< i l))
                  (set! sum (+ sum (x i)))
                  (set! lmax (max lmax sum)))
                (let ((rmax 0) (sum 0))
                  (do ((i (+ m 1) (+ i 1))) ((< u i))
                    (set! sum (+ sum (x i)))
                    (set! rmax (max rmax sum)))
                  (max (+ lmax rmax) (maxsum3 l m)
                       (maxsum3 (+ m 1) u))))))))))

(define (max-sum-subseq-4 xv)
  (let ((n (vector-length xv))
        (max-so-far 0)
        (max-ending-here 0))
    (do ((i 0 (+ i 1))) ((= i n) max-so-far)
      (set! max-ending-here (max (+ max-ending-here (vector-ref xv i)) 0))
      (set! max-so-far (max max-so-far max-ending-here)))))

(define (max-sum-subsequence xs)
  (let loop ((xs xs) (max-ending-here 0) (max-so-far 0))
    (if (null? xs) max-so-far
      (let ((max-ending-here (max (+ max-ending-here (car xs)) 0)))
        (loop (cdr xs) max-ending-here (max max-ending-here max-so-far))))))

(define xs '(31 -41 59 26 -53 58 97 -93 -23 84))
(define xv #(31 -41 59 26 -53 58 97 -93 -23 84))

(display (max-sum-subseq-1    xv)) (newline)
(display (max-sum-subseq-2a   xv)) (newline)
(display (max-sum-subseq-2b   xv)) (newline)
(display (max-sum-subseq-3    xv)) (newline)
(display (max-sum-subseq-4    xv)) (newline)
(display (max-sum-subsequence xs)) (newline)

187
187
187
187
187
187