Welcome,
Guest
. Please
login
or
register
.
1 Hour
1 Day
1 Week
1 Month
Forever
Login with username, password and session length
News:
Home
Help
Login
Register
TheSwamp
»
Code Red
»
AutoLISP (Vanilla / Visual)
»
Topic:
(Challenge) Max Sum of Sub Array
« previous
next »
Print
Pages:
1
[
2
]
All
|
Go Down
Author
Topic: (Challenge) Max Sum of Sub Array (Read 3542 times)
0 Members and 1 Guest are viewing this topic.
Lee Mac
Seagull
Posts: 12922
London, England
WWW
Re: (Challenge) Max Sum of Sub Array
«
Reply #15 on:
December 09, 2017, 10:22:29 AM »
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]
(
defun
LM_maxsublist
(
lst
/
idx rtn tmp
)
(
setq
rtn
(
list
(
car
lst
)
0
0
)
tmp rtn
idx
1
)
(
foreach
itm
(
cdr
lst
)
(
if
(
<
(
+
(
car
tmp
)
itm
)
itm
)
(
setq
tmp
(
list
itm idx idx
)
)
(
setq
tmp
(
list
(
+
(
car
tmp
)
itm
)
(
cadr
tmp
)
idx
)
)
)
(
if
(
<
(
car
rtn
)
(
car
tmp
)
)
(
setq
rtn tmp
)
)
(
setq
idx
(
1+
idx
)
)
)
rtn
)
Code - Auto/Visual Lisp:
[Select]
_$
(
LM_maxsublist '
(
1
9
-
6
5
-
9
3
2
-
7
4
-
5
8
-
2
6
)
)
(
12
10
12
)
_$
(
LM_maxsublist '
(
1
9
-
6
5
-
9
3
2
-
7
4
-
5
8
-
2
12
6
)
)
(
24
10
13
)
_$
(
LM_maxsublist '
(
2
-
2
-
2
3
)
)
(
3
3
3
)
Logged
Lee Mac Programming
•
Twitter
•
Exchange App Store
JohnK
Administrator
Seagull
Posts: 10655
Re: (Challenge) Max Sum of Sub Array
«
Reply #16 on:
December 09, 2017, 08:33:22 PM »
Please add comments to your code entries.
Logged
TheSwamp.org
(serving the CAD community since 2003)
Member location map - Add yourself
Donate to TheSwamp.org
roy_043
Water Moccasin
Posts: 1895
BricsCAD 18
Re: (Challenge) Max Sum of Sub Array
«
Reply #17 on:
December 10, 2017, 04:42:49 AM »
Lee's code shows that I have been seriously overthinking this.
Of course now I'll have to do some more thinking...
Logged
Lee Mac
Seagull
Posts: 12922
London, England
WWW
Re: (Challenge) Max Sum of Sub Array
«
Reply #18 on:
December 10, 2017, 07:01:25 AM »
Quote from: John Kaul (Se7en) on December 09, 2017, 08:33:22 PM
Please add comments to your code entries.
A commented version:
Code - Auto/Visual Lisp:
[Select]
(
defun
LM_maxsublist
(
lst
/
idx rtn tmp
)
;; Define function and declare arguments & local variables
;; Initialise variables
(
setq
;; 'rtn' holds the value that will eventually be returned by the function
rtn
(
list
(
car
lst
)
0
0
)
;; 'tmp' holds the comparison value to test whether each item improves the overall sum, initialised to the same value as 'rtn'
tmp rtn
;; Index variable initialised to 1 as we've already processed the first item
idx
1
)
;; end setq
;; For every other item in the list
(
foreach
itm
(
cdr
lst
)
;; If the item is greater than the current sum plus the item
(
if
(
<
(
+
(
car
tmp
)
itm
)
itm
)
;; Then all previous items would contribute negatively to the sum, so start the sublist at this item
(
setq
tmp
(
list
itm idx idx
)
)
;; Else add this item to the current sum and update the upper index
(
setq
tmp
(
list
(
+
(
car
tmp
)
itm
)
(
cadr
tmp
)
idx
)
)
)
;; end if
;; If the current sum is greater than our current maximum
(
if
(
<
(
car
rtn
)
(
car
tmp
)
)
;; Then update the current maximum as we've found something better
(
setq
rtn tmp
)
)
;; end if
;; Increment the index variable for each item processed
(
setq
idx
(
1+
idx
)
)
)
;; end foreach
;; Return the maximum sum obtained and corresponding indexes
rtn
)
;; end defun
Logged
Lee Mac Programming
•
Twitter
•
Exchange App Store
Print
Pages:
1
[
2
]
All
|
Go Up
« previous
next »
TheSwamp
»
Code Red
»
AutoLISP (Vanilla / Visual)
»
Topic:
(Challenge) Max Sum of Sub Array