Author Topic: (Challenge) Max Sum of Sub Array  (Read 3369 times)

0 Members and 1 Guest are viewing this topic.

JohnK

  • Administrator
  • Seagull
  • Posts: 10605
(Challenge) Max Sum of Sub Array
« on: December 07, 2017, 09:52:34 AM »
I found an old challenge that should be fun to revisit. This challenge was from a friend of mine (his post) but he is no longer a member here so I will post his words below instead of trying to find a link to his post. I found this in one of my old files with the description and my entry into the challenge (I will post my entry later).

As usual, please post your solution in any language but please add comments to your code so other people can learn from your solution.

*** Cornbread ***
Given the array { 1, 9, -6, 5, -9, 3, 2, -7, 4, -5, 8, -2, 6}

Write the most efficient function you can which returns the sum of the largest possible sub array value and that sub arrays start and end indexes. The array may not be re-ordered it must stay as is. This can be solved in O(n) or in regular language: a single pass over each element of the array.

This should test your algorithm writing abilities not your ability to use your favorite language.
*** Cornbread ***
TheSwamp.org (serving the CAD community since 2003)
Member location map - Add yourself

Donate to TheSwamp.org

JohnK

  • Administrator
  • Seagull
  • Posts: 10605
Re: (Challenge) Max Sum of Sub Array
« Reply #1 on: December 07, 2017, 11:00:29 AM »
Spoiler Alert!

EDIT: Note, this code submission is incorrect.
Below was the code I had for the answer to the challenge Cornbread posted.
Code - Auto/Visual Lisp: [Select]
  1. (defun MaxSumofSubArray (arr / item inx-start inx-end cntr)
  2.   (setq cntr 0
  3.         item (car arr))
  4.   (mapcar
  5.     '(lambda (x)
  6.        (if (> x item)
  7.          ;; if we have a bigger number then the one stored already,
  8.          (setq inx-start
  9.                ;; find the start index, but...
  10.                (if (= cntr 0)
  11.                  ;; if the item is the first item in the list, then
  12.                  ;; dont go lower then zero
  13.                  0
  14.                  (1- cntr) )
  15.                inx-end
  16.                ;; find the end index, but...
  17.                (if (eq cntr (1- (length arr)))
  18.                  ;; if the item is the last item in the list, then
  19.                  ;; dont go any higher then the length of the list
  20.                  (1- (length arr))
  21.                  (1+ (1+ cntr)) )
  22.                item x
  23.                cntr (1+ cntr)
  24.                )
  25.          ;; if we have a smaller number, then the one we have stored
  26.          (setq cntr (1+ cntr))
  27.          )
  28.        )
  29.     arr
  30.     )
  31.  (list item inx-start inx-end)
  32. )

EDIT: This return value is incorrect.
Code: [Select]
(MaxSumofSubArray '(1 9 -6 5 -9 3 2 -7 4 -5 8 -2 6))
(9 0 3)

EDIT: The correct return value should be: 12 10 12


« Last Edit: December 08, 2017, 08:05:13 AM by John Kaul (Se7en) »
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 #2 on: December 08, 2017, 05:53:47 AM »
I may have misunderstood, but shouldn't the answer be:
Code: [Select]
(10 0 1)?

JohnK

  • Administrator
  • Seagull
  • Posts: 10605
Re: (Challenge) Max Sum of Sub Array
« Reply #3 on: December 08, 2017, 07:18:18 AM »
I may not have had the correct answer saved in my old file but I remember us all writing several versions trying to find the right answer. It was a really fun and confusing challenge (that much I remember). This came from a professional CS, so I wouldn't expect it to be that easy.
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 #4 on: December 08, 2017, 07:32:51 AM »
So what should the answer be?

JohnK

  • Administrator
  • Seagull
  • Posts: 10605
Re: (Challenge) Max Sum of Sub Array
« Reply #5 on: December 08, 2017, 07:45:18 AM »
I'm trying to figure that out right now. Do you want just the answer or how I got that (my "key" so to speak) as well?
TheSwamp.org (serving the CAD community since 2003)
Member location map - Add yourself

Donate to TheSwamp.org

JohnK

  • Administrator
  • Seagull
  • Posts: 10605
Re: (Challenge) Max Sum of Sub Array
« Reply #6 on: December 08, 2017, 07:46:28 AM »
The correct answer/return value should be: 12 10 12
TheSwamp.org (serving the CAD community since 2003)
Member location map - Add yourself

Donate to TheSwamp.org

JohnK

  • Administrator
  • Seagull
  • Posts: 10605
Re: (Challenge) Max Sum of Sub Array
« Reply #7 on: December 08, 2017, 08:02:46 AM »
Now I understand the problem again I need to work on my code and I already see that I am missing a big chunk of it. I will try and get to redoing my code throughout the day.
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 #8 on: December 08, 2017, 10:05:28 AM »
OK. The answer should indeed be (12 10 12).

Here is my suggestion:
Code - Auto/Visual Lisp: [Select]
  1. ; (Roy_MaxSumofSubList '(1 9 -6 5 -9 3 2 -7 4 -5 8 -2 6))    => (12 10 12)
  2. ; (Roy_MaxSumofSubList '(1 9 -6 5 -9 3 2 -7 4 -5 8 -2 12 6)) => (24 10 13)
  3. (defun Roy_MaxSumofSubList (lst / idx ret sub tmp)
  4.   (setq idx 0)
  5.   (repeat (length lst)
  6.     (setq sub (reverse lst))
  7.     (repeat (1- (length sub))
  8.       (if (> (setq tmp (apply '+ sub)) (car ret))
  9.         (setq ret (list tmp idx (+ idx (length sub) -1)))
  10.       )
  11.       (setq sub (cdr sub))
  12.     )
  13.     (setq idx (1+ idx))
  14.     (setq lst (cdr lst))
  15.   )
  16.   ret
  17. )

roy_043

  • Water Moccasin
  • Posts: 1895
  • BricsCAD 18
Re: (Challenge) Max Sum of Sub Array
« Reply #9 on: December 08, 2017, 02:55:06 PM »
Another:
Code - Auto/Visual Lisp: [Select]
  1. (defun Roy_MaxSumofSubList_2 (lst / idx ret tmp)
  2.   (setq tmp (setq ret (list (car lst) 0 0)))
  3.   (setq idx 0)
  4.   (foreach itm (cdr lst)
  5.     (setq idx (1+ idx))
  6.     (cond
  7.       ((not tmp)
  8.         (setq tmp (list itm idx idx))
  9.       )
  10.       ((>= 0 (+ itm (car tmp)))
  11.         (setq tmp nil)
  12.       )
  13.       (T
  14.         (if (and (minusp itm) (> (car tmp) (car ret))) (setq ret tmp))
  15.         (setq tmp (list (+ itm (car tmp)) (cadr tmp) idx))
  16.       )
  17.     )
  18.   )
  19.   (if (> (car tmp) (car ret)) tmp ret)
  20. )

JohnK

  • Administrator
  • Seagull
  • Posts: 10605
Re: (Challenge) Max Sum of Sub Array
« Reply #10 on: December 08, 2017, 03:59:29 PM »
Nice ones!

I haven't been able to do much today (nose deep in specifications all day) after I initially tried to modify my code; I broke it several times just trying to add simple changes (boy, am I rusty!).
TheSwamp.org (serving the CAD community since 2003)
Member location map - Add yourself

Donate to TheSwamp.org

Lee Mac

  • Seagull
  • Posts: 12906
  • London, England
Re: (Challenge) Max Sum of Sub Array
« Reply #11 on: December 08, 2017, 04:23:40 PM »
Another:
Code - Auto/Visual Lisp: [Select]
  1. (defun Roy_MaxSumofSubList_2 (lst / idx ret tmp)
  2.     < ... >
  3. )

Very good Roy  :-)

VovKa

  • Water Moccasin
  • Posts: 1626
  • Ukraine
Re: (Challenge) Max Sum of Sub Array
« Reply #12 on: December 08, 2017, 05:38:09 PM »
Code: [Select]
(Roy_MaxSumofSubList_2 '(2 -2 -2 3))

Lee Mac

  • Seagull
  • Posts: 12906
  • London, England
Re: (Challenge) Max Sum of Sub Array
« Reply #13 on: December 08, 2017, 06:36:14 PM »
Quick fix could be:
Code - Auto/Visual Lisp: [Select]
  1. (if (< 0 itm) (setq tmp (list itm idx idx)))

Well spotted VovKa.

roy_043

  • Water Moccasin
  • Posts: 1895
  • BricsCAD 18
Re: (Challenge) Max Sum of Sub Array
« Reply #14 on: December 09, 2017, 05:15:36 AM »
Thank you all for your comments. :-)

Improved versions of my functions (the first one would also fail with VovKa's test case):
Code - Auto/Visual Lisp: [Select]
  1. ; (Roy_MaxSumOfSubList_1B '(1 9 -6 5 -9 3 2 -7 4 -5 8 -2 6))    => (12 10 12)
  2. ; (Roy_MaxSumOfSubList_1B '(1 9 -6 5 -9 3 2 -7 4 -5 8 -2 12 6)) => (24 10 13)
  3. ; (Roy_MaxSumOfSubList_1B '(2 -2 -2 3))                         => (3 3 3)
  4. (defun Roy_MaxSumOfSubList_1B (lst / idx ret sub tmp)
  5.   (setq idx 0)
  6.   (repeat (length lst)
  7.     (setq sub (reverse lst))
  8.     (repeat (length sub)
  9.       (if (> (setq tmp (apply '+ sub)) (car ret))
  10.         (setq ret (list tmp idx (+ idx (length sub) -1)))
  11.       )
  12.       (setq sub (cdr sub))
  13.     )
  14.     (setq idx (1+ idx))
  15.     (setq lst (cdr lst))
  16.   )
  17.   ret
  18. )
  19.  
  20. ; (Roy_MaxSumOfSubList_2B '(1 9 -6 5 -9 3 2 -7 4 -5 8 -2 6))    => (12 10 12)
  21. ; (Roy_MaxSumOfSubList_2B '(1 9 -6 5 -9 3 2 -7 4 -5 8 -2 12 6)) => (24 10 13)
  22. ; (Roy_MaxSumOfSubList_2B '(2 -2 -2 3))                         => (3 3 3)
  23. (defun Roy_MaxSumOfSubList_2B (lst / idx ret tmp)
  24.   (setq tmp (setq ret (list (car lst) 0 0)))
  25.   (setq idx 0)
  26.   (foreach itm (cdr lst)
  27.     (setq idx (1+ idx))
  28.     (cond
  29.       ((not tmp)
  30.         (setq tmp (list itm idx idx))
  31.       )
  32.       ((>= 0 (+ itm (car tmp)))
  33.         (setq tmp nil)
  34.       )
  35.       ((and (>= 0 (car tmp)) (> itm (car tmp)))
  36.         (setq tmp (list itm idx idx))
  37.       )
  38.       (T
  39.         (if (and (>= 0 itm) (> (car tmp) (car ret))) (setq ret tmp))
  40.         (setq tmp (list (+ itm (car tmp)) (cadr tmp) idx))
  41.       )
  42.     )
  43.   )
  44.   (if (> (car tmp) (car ret)) tmp ret)
  45. )