Topic: (Challenge) Max Sum of Sub Array

[Lee Mac]

Extending Roy's method, rather than testing for negation, I think the loop could be reduced to testing whether the next element improves the overall sum, i.e.:

Code - Auto/Visual Lisp: [Select]

1. (defun LM_maxsublist ( lst / idx rtn tmp )
2.     (setq rtn (list (car lst) 0 0)
3.           tmp rtn
4.           idx 1
5.     )
6.     (foreach itm (cdr lst)
7.         (if (< (+ (car tmp) itm) itm)
8.             (setq tmp (list itm idx idx))
9.             (setq tmp (list (+ (car tmp) itm) (cadr tmp) idx))
10.         )
11.         (if (< (car rtn) (car tmp)) (setq rtn tmp))
12.         (setq idx (1+ idx))
13.     )
14.     rtn
15. )

Code - Auto/Visual Lisp: [Select]

1. _$ (LM_maxsublist '(1 9 -6 5 -9 3 2 -7 4 -5 8 -2 6))
2. (12 10 12)
3. _$ (LM_maxsublist '(1 9 -6 5 -9 3 2 -7 4 -5 8 -2 12 6))
4. (24 10 13)
5. _$ (LM_maxsublist '(2 -2 -2 3))
6. (3 3 3)

[JohnK]

Please add comments to your code entries.

[roy_043]

Lee's code shows that I have been seriously overthinking this.
Of course now I'll have to do some more thinking...

[Lee Mac]

Please add comments to your code entries.

A commented version:

Code - Auto/Visual Lisp: [Select]

1. (defun LM_maxsublist ( lst / idx rtn tmp )
2.     ;; Define function and declare arguments & local variables
3.  
4.     ;; Initialise variables
5.     (setq
6.         ;; 'rtn' holds the value that will eventually be returned by the function
7.         rtn (list (car lst) 0 0)
8.         ;; 'tmp' holds the comparison value to test whether each item improves the overall sum, initialised to the same value as 'rtn'
9.         tmp rtn
10.         ;; Index variable initialised to 1 as we've already processed the first item
11.         idx 1
12.     ) ;; end setq
13.  
14.     ;; For every other item in the list
15.     (foreach itm (cdr lst)
16.         ;; If the item is greater than the current sum plus the item
17.         (if (< (+ (car tmp) itm) itm)
18.             ;; Then all previous items would contribute negatively to the sum, so start the sublist at this item
19.             (setq tmp (list itm idx idx))
20.             ;; Else add this item to the current sum and update the upper index
21.             (setq tmp (list (+ (car tmp) itm) (cadr tmp) idx))
22.         ) ;; end if
23.  
24.         ;; If the current sum is greater than our current maximum
25.         (if (< (car rtn) (car tmp))
26.             ;; Then update the current maximum as we've found something better
27.             (setq rtn tmp)
28.         ) ;; end if
29.  
30.         ;; Increment the index variable for each item processed
31.         (setq idx (1+ idx))
32.     ) ;; end foreach
33.  
34.     ;; Return the maximum sum obtained and corresponding indexes
35.     rtn
36. ) ;; end defun