Steve the Gambler = Follow up

The puzzle if you recall, requires you to find the largest subvector sum in an array. i.e. the largest consecutive grouping of array elements. The solution is extremely simple, when you know how . It is a classic trap puzzle though, most people approach it presuming it is extremely difficult and therefore reach into their bag of "USE ONLY IN CASE OF EMERGENCY" tools, and come out with Recursion, Binary Trees, Reductions, Complexity Theory, none of which are necessary to solve this problem. In fact every single one of them will produce more problems than they solve, similar to what Jamie Zawinski allegedly said about regular expressions...

Some people, when confronted with a problem, think “I know, I’ll use regular expressions.” Now they have two problems.

Complicated solutions pose 2 problems, firstly people presume they are correct because they are so difficult to understand, and secondly the author is quite often proud of them and hence won't look to refine or simplify them. So, to cut to chase, Yes it is solveable. It is solvable in O(N), and the algorithm looks depressing simple in any language (well, not ANY language, we'll get to that later). Here is a short and sweet solution in Java...

1. int v[]={44 ... 1};
2. int MaxSoFar =0;
3. int MaxEndingHere = 0;
4. for(int i=0;i<v.length;i++)
5. {
6.    MaxEndingHere = Math.max(MaxEndingHere+v[i], 0);
7.    MaxSoFar = Math.max(MaxSoFar, MaxEndingHere);
8. }
9. System.out.println("The maximum Steve can earn is: " + MaxSoFar);

Obviously you need to add 2 more variables to keep track of the start and end dates. The answer for the numbers posted in original puzzle is 383

The commenters

Thanks to everyone who had comments. I wasn't aware this was a well known "classic" programming puzzle, that much I am ashamed to admit, at least I know it now Many people posted code in the comments, which serendipity tends to mangle, so I have reformatted the submissions, and here they are...

• C# from Jacob Profitt O(n^2)
  1. {
  2.   string[] split = numbersTextBox.Text.Split(new char[] { ',' });
  3.   List < double > numbers = new List < double > ();
  4.   double tempDouble = 0;
  5.   foreach (string tempString in split)
  6.   {
  7.     if(double.TryParse(tempString, out tempDouble))
  8.       {
  9.        numbers.Add(tempDouble);
  10.       }
  11.   }
  12.   if(numbers.Count > 0)
  13.   {
  14.     double bestSum = 0, sum;
  15.     int bestStart = 0, bestStop = 0, start, stop;
  16.     for (start = 0; start < numbers.Count; start++)
  17.     {
  18.       sum = 0;
  19.         for (stop = start; stop < numbers.Count; stop++)
  20.         { 
  21.            sum += numbers[stop];
  22.            if(sum > bestSum)
  23.              {
  24.                bestStart = start;
  25.                bestStop = stop;
  26.                bestSum = sum;
  27.              }
  28.         }
  29.     }
  30.   }
  31. }
  32. resultsLabel.Text = string.Format("The best sum was achieved
  33. by beginning at position {0} (value {1}) and continuing
  34. to position {2} (value {3}) for a sum of {4}.", bestStart + 1,
  35. numbers[bestStart], bestStop + 1, numbers[bestStop], bestSum);
• The Pseudocode algorithm from the Programming Pearls book, by Anonymous
  1. maxsofar = 0
  2. maxendinghere = 0
  3. for i = [0,n)
  4.   maxendinghere = max(maxendinghere + x[i], 0)
  5.   maxsofar = max(maxsofar, maxendinghere)
• A C/C++ version from vyger
  1. int main(int argc, char **argv)
  2. {
  3.   int a[30] = {432, ... }
  4. int t, x, n, z;
  5. t = x = n = z = 0;
  6.  for(int i = 0; i < 30; i++)
  7.  {
  8.      t += a[i];
  9.      printf("%d ", t);
  10.      if (t < z) z = t;
  11.      if (t - z > x - n) {x = t; n = z;}
  12.      if (t > x) {x = t; n = z;}
  13.  }
  14. printf("%d", x - n);
  15. }
• A LISP version by Michael Mills.
  1. (defun max-set (numbers result-function combiner-function test-function)
  2.   (do*
  3.   ( (number numbers (cdr number))
  4.     (result (apply result-function (list number)) (apply result-function (list number)))
  5.     (current result (apply combiner-function `(,current ,result)))
  6.     (max current (if (apply test-function `(,current ,max)) current max)))
  7.   ((endp (cdr number)) max)))
  8. (max-set
  9.   `(432 90 ... -395)
  10.   #'(lambda (numbers) (max-set numbers #'car #'+ #'>))
  11.   #'(lambda (&rest numbers) (cadr numbers)
  12.   #'>)
• A Haskell Version by Jules...
  1. maxseq xs = foldr1 max (map ((foldr1 max) . (map sum) . (scanr (:) []) . reverse) (scanr (:) [] xs))
• Another LISP version, by Anders
  1. (defun max-subsequence (numbers)
  2.   (setq m 0)
  3.   (setq p 0)
  4.   (dolist (element numbers m)
  5.    (setq p (max 0 (+ p element)))
  6.    (setq m (max m p))))

Thats not all the submissions, but I got tired of formatting them . I think it shows a nice comparison of the differences in programming languages. The last one was called Are all programming languages the same?. Anyways, thats all for now. Thanks for reading/commenting.