codepad
[
create a new paste
]
login
|
about
Language:
C
C++
D
Haskell
Lua
OCaml
PHP
Perl
Plain Text
Python
Ruby
Scheme
Tcl
; 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)
Private
[
?
]
Run code
Submit