package org.wesome.dsalgo;
import java.util.Arrays;
public class Kadane {
public static int maximumSumSubArray(int[] arr) {
int maxSum = Integer.MIN_VALUE, currentSum = 0, start = 0, startIndx = 0, end = 0;
for (int indx = 0; indx <= arr.length - 1; indx++) {
currentSum = currentSum + arr[indx];
if (currentSum > maxSum) {
maxSum = currentSum;
start = startIndx;
end = indx;
}
if (currentSum < 0) {
currentSum = 0;
startIndx = indx + 1;
}
}
System.out.println(" start indx " + startIndx + " end indx " + end + " " + Arrays.toString(Arrays.copyOfRange(arr, start, end)));
return maxSum;
}
}
package org.wesome.dsalgo;
import org.junit.jupiter.api.Assertions;
import org.junit.jupiter.api.Test;
import static org.wesome.dsalgo.Kadane.maximumSumSubArray;
public class KadaneTest {
@Test
public void maximumSumSubArrayTest1() {
int arr[] = {1, 3, 8, -2, 6, -8, 5};
Assertions.assertEquals(16, maximumSumSubArray(arr));
}
@Test
public void maximumSumSubArrayTest2() {
int arr[] = {-2, -3, 4, -1, -2, 1, 5, -3};
Assertions.assertEquals(7, maximumSumSubArray(arr));
}
@Test
public void maximumSumSubArrayTest3() {
int arr[] = {-3, -2, -1, 0, 1, 2, 3};
Assertions.assertEquals(6, maximumSumSubArray(arr));
}
@Test
public void maximumSumSubArrayTest4() {
int arr[] = {1, -1, 2, -2, 3, -3, 4, -4};
Assertions.assertEquals(4, maximumSumSubArray(arr));
}
}
plugins {
id 'java'
id "io.freefair.lombok" version "6.2.0"
}
group = 'org.wesome'
version = '0.0.1-SNAPSHOT'
sourceCompatibility = JavaVersion.VERSION_1_8
configurations {
compileOnly {
extendsFrom annotationProcessor
}
}
repositories {
mavenCentral()
}
dependencies {
testImplementation 'org.junit.jupiter:junit-jupiter:5.6.2'
}
test {
useJUnitPlatform()
}