Given a list that contains both positive and negative integers, find the product of the maximum product sublist.
Code: Select all
(define (maxProd lst)
(local (n maxprod pos neg)
(setq n (length lst))
(setq pos (array n '(0)))
(setq neg (array n '(0)))
(setq (pos 0) (lst 0)) ; pos[i] contains the positive product up to lst[i]
(setq (neg 0) (lst 0)) ; neg[i] contains the negative product up to lst[i]
(setq maxprod (lst 0))
(for (i 0 (- n 1))
; the maximum of the three values
(setq (pos i) (max (max (* (pos (- i 1)) (lst i)) (* (neg (- i 1)) (lst i))) (lst i)))
; the minimum of the three values
(setq (neg i) (min (min (* (pos (- i 1)) (lst i)) (* (neg (- i 1)) (lst i))) (lst i)))
(setq maxprod (max maxprod (pos i)))
)
maxprod
)
)
(setq lst '(6 -3 -10 0 2))
(maxProd lst)
;-> 180
Sublist: (6 -3 -10)
(setq lst '(-1 -3 -10 0 60))
(maxProd lst)
;-> 60
Sublist: (60)
(setq lst '(-2 -3 0 -2 -40))
(maxProd lst)
;-> 80
Sublist: (-2 -40)
(setq lst '(-1 -2 -3))
(maxProd lst)
;-> 6
(setq lst '(0 -1))
(maxProd lst)
;-> 0
(setq lst '(0 0 0 0))
(maxProd lst)
;-> 0
cameyo
p.s. The "Maximum Sum sublist" problem is solved with the Kadane algorithm