max-sum.md

• From Joshua Harris in python (gist)

• From Denis Karpenko in Ruby (with rspec tests!) (gist)

• From Nikki DelRosso in python (gist):

  

  "And an explanation of the solution (since the Python is very dense): For each value, since we're doing sums consecutively, we want to calculate the maximum that we could attain if we use the current value as the last value in the sequence. The only information we need to calculate this was what the maximum value was if we ended on the value before this in the sequence. If the previous value was negative, then the max value attainable by ending on this value is just this value. Otherwise, we add the current with the value for the previous element. All we need, then, is to iterate through our sequence and keep track of the previous best option, as well as the maximum consecutive we've seen thus far.

  My code doesn't keep any meta-information about where this sequence is. It could be added by keeping track of an index while iterating through the sequence, and using a tuple for the prev value (sequence start, max value ending with previous) and a triple for the m value (sequence start, sequence end, max value).

  This solution is linear time, and uses minimal memory."

• Clojure solution from Paul Bostrom (gist)—and neat clojure REPL that Paul built

  If you are looking for a clojure programmer in the Austin, TX area you can reach out to Paul at pbostrom at gmail.com

• Jason Tu's C++ notes (imgur 1, imgur 2) and solution (gist)

  

• Dimitris Leventeas' C++ solution (gist), who notes: "You could do it using O(1) space also, but it makes no difference in time complexity."

• Arun Padmanabhan's C solution

  

• Florent Crivello's Objective-C solution (gist), who notes: "Yep, it's in Objective-C. Things are funnier in Objective-C." (agreed!)

• Max Lesser's Java solution (gist)

• Gregory Chu's Java solution (gist)

• Ankit Goyal's C++ solution (gist)

• Amit Matani's python solution (gist)

• Albert Elwin's C++ solution (gist)—Albert just released a new awesome looking egame: http://www.desura.com/games/903m

• Swapnil Mhatre's python solution (gist)

• Davit Khaburdzania's ruby solution (gist)

• Mathew Moore's python solution (gist Mat notes: "I scan the list by always expanding to the right, and dropping elements from the left whenever the sum goes negative. At the end of the loop the highest sum seen is the highest in the array."

• Jeff Carpenter's lisp solution (gist, imgur)—who CHEATED by looking up Kadane's algorithm (-10 points from Gryffindor)... then totally told the truth about it (+20 points to Gryffindor)!!!

  

• Antti Pöyhönen's javascript solution (gist)

• Antonio Moragón Juan's erlang solution (gist)

• Sunil Shah's Java solution (gist)

• Anup Sawant's Java solution (gist Anup is looking for jobs in the Chicago area, and can be reached at anupsatishsawant at gmail.com

• Rohit Jamuar's python solution (gist)

• Maximo Vezzosi's ruby solution (gist)

• Kevin Zhao's python solution (gist) and epic PDF writeup (imgur)

Here is a Scala solution:

def maxSubArraySum(s: Seq[Int]) = s.scanLeft(0)((sum, i) => (sum + i) max 0).max

Kadane's algorithm in Java: https://gist.github.com/dmnugent80/6e048f639096f118a16d