0053-maximum-subarray.rkt

#lang racket

; (define/contract (max-sub-array nums)
;   (-> (listof exact-integer?) exact-integer?)
;   (for/fold ([prevacc 0] [minacc 0] [ans (car nums)] #:result ans)
;             ([ni (in-list nums)])
;     (define acc (+ prevacc ni))
;     (values acc (min minacc acc) (max ans (- acc minacc)))))

(define/contract (max-sub-array nums)
  (-> (listof exact-integer?) exact-integer?)
  (struct status (left-sum right-sum max-sum all-sum))
  (define (pushup left-status right-status)
    (define all-sum (+ (status-all-sum left-status) (status-all-sum right-status)))
    (define left-sum (max (status-left-sum left-status)
                          (+ (status-all-sum left-status) (status-left-sum right-status))))
    (define right-sum (max (status-right-sum right-status)
                           (+ (status-all-sum right-status) (status-right-sum left-status))))
    (define max-sum (max (status-max-sum left-status)
                         (status-max-sum right-status)
                         (+ (status-right-sum left-status) (status-left-sum right-status))))
    (status left-sum right-sum max-sum all-sum))
  (define v (list->vector nums))
  (define (get l r)
    (if (= l r)
        (let ([vi (vector-ref v l)])
          (status vi vi vi vi))
        (let ([m (quotient (+ l r) 2)])
          (pushup (get l m) (get (add1 m) r)))))
  (status-max-sum (get 0 (sub1 (vector-length v)))))