Take the 2-minute tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.

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

Updated Code: Based on the comments, the simplified code is:

class Kadane {
public static void main(String[] args) {
    int[] arr = {1,2,3,4,5,6,7,8,9,10,-60,54,3};
    System.out.print(Kadane.maximum(arr));
}

public static int maximum(int[] arr){
    int maximum_so_far = 0;
    int overall_maximum = 0;        
    for(int element:arr){
      maximum_so_far = Math.max(0, maximum_so_far + element);
      overall_maximum = Math.max(maximum_so_far, overall_maximum);
    }       
    return overall_maximum;
}

}

share|improve this question
add comment

1 Answer 1

up vote 4 down vote accepted

Ok, lets 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)


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 calculcate the sum from index 0 to index 0
In the 2. loop iteration, we check calculcate the sum from index 1 to index 0
In the 3. loop iteration, we check calculcate 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. So we have:

    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 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.

share|improve this answer
    
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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.