Kadane算法在Scheme（球拍）

Question

我理解Kadane的算法（數組中所有順序子數組的最大總和）是如何工作在「僞代碼」中的，並且我確信我可以將它作爲在C或C++中的函數。不過，我試圖使用Scheme（球拍;文件擴展名爲.rkt）中的列表來實現它，這是我沒有經驗的。

最終的結果我要找的是...

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

到目前爲止，我已經開發了兩個輔助功能我也許能夠在maxsum函數中使用。

（1）size：返回列表中元素的數量。

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

（2）sum：返回列表中所有元素的總和。

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

我該如何去定義/設計maxsum函數？

Answer 1

這裏是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 

它是尾遞歸，所以它會被編譯成一個有效的迭代程序。

(define (max_subarray A) 
    (define-values (max_ending_here max_so_far) (values 0 0)) 
    (for ((x (in-list A))) 
    (set! max_ending_here (max 0 (+ max_ending_here x))) 
    (set! max_so_far (max max_so_far max_ending_here))) 
    max_so_far) 

測試：

Answer 2

的[Python代碼] [1]到球拍幾乎直譯

(max_subarray `(1 4 -2 1)) 
(max_subarray '(-2 1 -3 4 -1 2 1 -5 4)) 

輸出：

5 
6 

請注意，遞歸函數一般在Racket中優先於迭代的，並且在這裏不鼓勵使用「set!」。

繼使用高功能化等apply和map爲不同的步驟：

(define (maxsum lst) 
    (define subarrays 
    (for*/list ((start (length lst)) 
       (len (range 1 (- (add1(length lst)) start)))) 
     (take (drop lst start) len))) 
    (define sumlist (map (λ (x) (apply + x)) subarrays)) 
    (apply max sumlist)) 

下面是更詳細的形式：

(define (maxsum lst) 
    (define subarrays 
    (for*/list ((start (length lst)) 
       (len (range 1 (- (add1(length lst)) start)))) 
     (take (drop lst start) len))) 
    (displayln "\n----- SUBARRAYS ---------") 
    (displayln subarrays) 
    (define sumlist (map (λ (x) (apply + x)) subarrays)) 
    (displayln "----- SUMS OF SUBARRAYS ---------") 
    (displayln sumlist) 
    (display "MAX SUM:") 
    (apply max sumlist)) 

測試：

(maxsum `(1 4 -2 1)) 
(maxsum '(-2 1 -3 4 -1 2 1 -5 4)) 

輸出：

----- SUBARRAYS --------- 
((1) (1 4) (1 4 -2) (1 4 -2 1) (4) (4 -2) (4 -2 1) (-2) (-2 1) (1)) 
----- SUMS OF SUBARRAYS --------- 
(1 5 3 4 4 2 3 -2 -1 1) 
MAX SUM:5 

----- SUBARRAYS --------- 
((-2) (-2 1) (-2 1 -3) (-2 1 -3 4) (-2 1 -3 4 -1) (-2 1 -3 4 -1 2) (-2 1 -3 4 -1 2 1) (-2 1 -3 4 -1 2 1 -5) (-2 1 -3 4 -1 2 1 -5 4) (1) (1 -3) (1 -3 4) (1 -3 4 -1) (1 -3 4 -1 2) (1 -3 4 -1 2 1) (1 -3 4 -1 2 1 -5) (1 -3 4 -1 2 1 -5 4) (-3) (-3 4) (-3 4 -1) (-3 4 -1 2) (-3 4 -1 2 1) (-3 4 -1 2 1 -5) (-3 4 -1 2 1 -5 4) (4) (4 -1) (4 -1 2) (4 -1 2 1) (4 -1 2 1 -5) (4 -1 2 1 -5 4) (-1) (-1 2) (-1 2 1) (-1 2 1 -5) (-1 2 1 -5 4) (2) (2 1) (2 1 -5) (2 1 -5 4) (1) (1 -5) (1 -5 4) (-5) (-5 4) (4)) 
----- SUMS OF SUBARRAYS --------- 
(-2 -1 -4 0 -1 1 2 -3 1 1 -2 2 1 3 4 -1 3 -3 1 0 2 3 -2 2 4 3 5 6 1 5 -1 1 2 -3 1 2 3 -2 2 1 -4 0 -5 -1 4) 
MAX SUM:6