1031-maximum-sum-of-two-non-overlapping-subarrays.rkt

#lang racket

(define/contract (max-sum-two-no-overlap nums firstLen secondLen)
  (-> (listof exact-integer?) exact-integer? exact-integer? exact-integer?)
  (define l (length nums))
  (define pre-sum (make-vector (add1 l)))
  (let ([s 0])
    (for ([(x i) (in-indexed (in-list nums))])
      (set! s (+ s x))
      (vector-set! pre-sum (add1 i) s)))
  (define (range-sum i1 i2)
    (- (vector-ref pre-sum i2) (vector-ref pre-sum i1)))
  (define (max-sum l1 l2)
    (for/fold ([max-l1 0] [max-l1l2 0] #:result max-l1l2)
              ([i (in-inclusive-range l1 (- l l2))])
      (define new-l1 (range-sum (- i l1) i))
      (define new-l2 (range-sum i (+ i l2)))
      (define new-max-l1 (max max-l1 new-l1))
      (define new-max-l1l2 (max max-l1l2 (+ new-max-l1 new-l2)))
      (values new-max-l1 new-max-l1l2)))
  (max (max-sum firstLen secondLen) (max-sum secondLen firstLen)))

; (max-sum-two-no-overlap '[0 6 5 2 2 5 1 9 4] 1 2)
(max-sum-two-no-overlap '[2 1 5 6 0 9 5 0 3 8] 4 3)