-1

我了解 Kadane 算法（数组中所有顺序子数组的最大总和）如何在“伪代码”中工作的逻辑，并且我确信我可以将它实现为 C 或 C++ 中的函数。但是，我正在尝试使用 Scheme（Racket；文件扩展名是 .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 函数？

4

2 回答 2

0

这是一个仿照 wikipedia 上 Phyton 代码的版本：

(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

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

于 2016-11-25T22:08:53.980 回答
0

[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
于 2016-11-26T01:12:28.953 回答