re
run
.
me

Find Continuous Subarray With Maximum Sum Problem - Kadane's Algorithm

Update : Previous version of the code failed for some inputs, as pointed out by @Thinker in the first comment. Changes to the program and the presentation were made. Tested to satisfy most conditions that I could google for.


In a desperate attempt to increase my sad looking stackoverflow reputation, I replied to an old but interesting problem.

The problem goes like this :

Given Random integers in array. Find the greatest sum of a continuous subset

The problem is otherwise known as the Maximum subarray problem and is beaten to death numerous times.

Kadane maximum sum subarray problem

So, instead of just translating a Python program into Java, I decided to pull together some slides which explains how this algorithm works.

And to bore you to death, here is the Java version of the modified algorithm :

Rajesh was kind enough to write the implementation in Scala. Sweet huh?

Comments