Largest Sum Contiguous Subarray - Kadene's algorithm

Question

I am looking forward to an answer to improve this code?

Thanks.

Test class

package test; import main.algorithms.LargestSumContiguousSubarray; import org.junit.Assert; import org.junit.Before; import org.junit.Test; public class LargestSumContiguousSubarrayTest { LargestSumContiguousSubarray largestSumContiguousSubarray; @Before public void setUp(){ largestSumContiguousSubarray = new LargestSumContiguousSubarray(); } @Test public void testSumContiguousSubArray(){ int[] a = {-2, -3, 4 - 1, -2, 1, 5, -3}; int sum = 7; Assert.assertEquals(sum, largestSumContiguousSubarray.kadenesAlgo(a)); } } 

LargestSumContiguousSubarray.java class

package main.algorithms; public class LargestSumContiguousSubarray { // O(n) // Kadene's algorithm public int kadenesAlgo(int[] a) { // This is also works for negative numbers int max_so_far = a[0]; int curr_max = a[0]; for(int i=0;i<a.length; i++){ curr_max = Math.max(a[i], curr_max+a[i]); max_so_far = Math.max(max_so_far, curr_max); } return max_so_far; } } 

Answer 1

@Doi9t 's answer already covered the ways how to improve your code. The first iteration of your for loop will return these assignments:

curr_max = a[0] //inside your loop curr_max = Math.max(a[0], curr_max + a[0]); max_so_far = Math.max(a[0], curr_max); 

So the first iteration will return a value of max_so_far equal to 2 * a[0] if a[0] >= 0 or a[0] if a[0] < 0 and this is a bug, for example your method for array {1} will return the value 2. I have seen from wikipedia that the algorithm set your variables max_so_far and curr_max to 0, this would solve the bug of your code.

Answer 2

I have some suggestions for your code.

Replace the for loop with an enhanced 'for' loop

In your code, you don’t actually need the index provided by the loop, you can use the enhanced version.

before

for (int i = 0; i < a.length; i++) { //[...] } 

after

for (int current : a) { //[...] } 

Variable and parameter name should be in camelCase style

The variables should be in camelCase.