# Kadane's Algorithm, finding maximum contiguous array

class Kadane {
int sum = 0;
int max = 0;

public static void main(String[] args) {
int[] full = { 1, 2, 3, 4, 5, -6, -77, 3, 14, -10 };
System.out.println("The maximum value of the seq is " + max);
}

public int localMax(int[] full, int sublength) {
for (int i = sublength; i >= 0; i--) {
sum = sum + full[i];
if (sum > max) {
max = sum;
}
}
sum = 0;
return max;
}

public int splitArr(int[] full) {
int sum_final = 0;
int max_final = 0;
for (int j = 0; j < full.length; j++) {
sum_final = localMax(full, j);
if (sum_final > max_final) {
max_final = sum_final;
}
}

return max_final;
}
}

-

Ok, let's take a look:

Kadane Kadane = new Kadane();


If there is no need for it, I would use static methods and avoid object creation:

public static int localMax(int[] full, int sublength) {...}
public static int splitArr(int[] full) {...}
int max = splitArr(full);
//(+ next point)


int sum = 0;
int max = 0;


I do not see the reason why they are class variables? You could use them in the method scope and have 2 benefits:

1. You do not have any state inside your class, which makes the methods recallable.
2. You can be sure nobody starts to modify it somewhere.

public int localMax(int[] full, int sublength) {
final int sum = 0;
final int max = 0;
//...
}


public int splitArr(int[] full)


This is a bad name. If someone reads only the method name, it is impossible to figure out what this is doing. You would expect to split an array? Then you would expect to get back one or multiple arrays. But you get an int.
A better method name could be:

public int getMaximumSumOfAllSubarraysFromArray(final int[] array)


(same goes for localMax)

if (sum > max) {
max = sum;
}
//...
if (sum_final > max_final) {
max_final = sum_final;
}


You could write:

max = Math.max(max, sum);
max_final = Math.max(max_final, sum_final);


Which makes the intention directly clear.

If we take this line:

sum_final = localMax(full, j);


You could inline the function localMax:

public int splitArr(final int[] full) {
int sum_final = 0;
int max_final = 0;
for (int j = 0; j < full.length; j++) {
int sum = 0;
for (int i = j; i >= 0; i--) {
sum = sum + full[i];
sum_final = Math.max(sum_final, sum);
}
max_final = Math.max(max_final, sum_final);
}

return max_final;
}


Then we look what is happening here:

• In the 1. loop iteration, we check calculate the sum from index 0 to index 0
• In the 2. loop iteration, we check calculate the sum from index 1 to index 0
• In the 3. loop iteration, we check calculate the sum from index 2 to index 0

We can see a pattern here. We do not have to do all the calculations from previous sums, we just use the previous result and add the new current element:

int sum = 0;
for (int j = 0; j < full.length; j++) {
sum = sum_final + full[i];
sum_final = Math.max(0, sum);
max_final = Math.max(max_final, sum_final);
}

1. Good thing: We got rid of the O(n^2) complexity back to O(n).
2. Good thing: we can simplify it even more. The variable sum is not necessary and we can use a foreach:

public int splitArr(final int[] full) {
int sum_final = 0;
int max_final = 0;
for (final int element : full) {
sum_final = Math.max(0, sum_final + element);
max_final = Math.max(max_final, sum_final);
}
return max_final;
}


We can choose some better names for all the variables and if we apply all the mentioned things we could end up with:

public static int getMaximumSumOfAllSubarraysFromArray(final int[] array) {
int currentMaximum = 0;
int overallMaximum = 0;
for (final int arrayItem : array) {
currentMaximum = Math.max(0, currentMaximum + arrayItem);
overallMaximum = Math.max(overallMaximum, currentMaximum);
}
return overallMaximum;
}


(which is by the way the same algorithm as mentioned from the Wikipedia link, and I think the best one for single thread, typical environments. It could be improved by removing the first Math.max, merging the branches and saving a little part of branching, but this would reduce readability):

public int getMaximumSumOfAllSubarraysFromArray(final int[] array) {
int currentMaximum = 0;
int overallMaximum = 0;
for (final int arrayItem : array) {
currentMaximum = currentMaximum + arrayItem;
if (currentMaximum > 0)
overallMaximum = Math.max(overallMaximum, currentMaximum);
else
currentMaximum = 0;
}
return overallMaximum;
}


One last piece of advice: If you develop such algorithms and refactor them, you should always have some unit tests for this. Better more than less.

I hope you can combine this hints to a full working approach. If not, just mention the flaws in my descriptions.

-
Thanks for the detailed code review. I updated the code. I have to learn unit testing. I will post another code review question and get my unit tested code reviewed. –  redmave Feb 3 '13 at 21:20
You are welcome. If you use eclipse, it is very easy to do unit tests with junit. Read some tutorials, this will take less then 5 minutes to create a first test. Try eclemma.org eclipse plugin for coverage. As always with metrics, it is not all about 100% coverage, but you have some feedback. Design unit tests for different corner case, not different inputs (to make an example here: if you test [1,2,3], then there is no extra value in testing [2,2,3], but for [2,-1,2]). –  tb- Feb 3 '13 at 21:59
Hi tb. Is there a way to contact you privately. I have a quick question. –  redmave May 2 '13 at 17:16
I do not know if there is a way to send private messages on codereview. –  tb- May 5 '13 at 22:30