Find Maximum Contiguous Sum Sub Array Kadane algorithm

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

 

follow us on