Scheme中Kadane的算法（Racket）

Question

我了解 Kadane 算法（数组中所有顺序子数组的最大总和）在 "pseudo-code," 中的工作原理，我确信我可以将其作为 C 或 C++ 中的函数来实现。但是，我正在尝试使用 Scheme 中的列表（Racket；文件扩展名为 .rkt）来实现它，我对此没有任何经验。

我要寻找的最终结果是...

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

到目前为止，我已经开发了两个可以在 maxsum 函数中使用的辅助函数。

(1) 大小：returns 列表中的元素数。

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

(2) sum: returns 列表中所有元素的总和。

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

我将如何处理 defining/designing 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

它是尾递归的，所以会编译成一个高效的迭代程序。

Answer 2

[Python 代码][1] 的几乎直译为 Racket：

(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)

测试：

(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

Scheme中Kadane的算法（Racket）

Kadane's Algorithm in Scheme (Racket)

algorithm

scheme

racket

kadanes-algorithm