Kadane’s Algorithm, finding maximum contiguous array

Question 1

Description of Kadane’s algorithm.
Please comment on the efficiency and approach.

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 };
    Kadane Kadane = new Kadane();
    int max = Kadane.splitArr(full);
    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;
}
}

Question 2

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:

You do not have any state inside your class, which makes the methods recallable.

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)

Instead of:

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);
}

Good thing: We got rid of the O(n^2) complexity back to O(n).

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.

Leave a Reply Cancel reply