MaxSubarraySumKadanes.java

packagegfg.Arrays;

publicclassMaxSubarraySumKadanes {

publicstaticvoidmain(String[] args) {

int[] arr = { 3, 1, 5, -2, -4, 6 };
System.out.println("max sum is: " + kadanesAlgo(arr)); // 9

int[] arr2 = { -6, -1, -8 };
System.out.println("max sum is: " + kadanesAlgo(arr2)); // -1

int[] arr3 = { 1, 2, 3 };
System.out.println("max sum is: " + kadanesAlgo(arr3)); // 6
 }

// O(n) Time | O(1) Space
publicstaticintkadanesAlgo(int[] arr) {
intresult = Integer.MIN_VALUE;
intcurrSum = 0;

for (inti = 0; i < arr.length; i++) {
currSum += arr[i];

if (currSum > result) {
result = currSum;
 }
if (currSum < 0) {
currSum = 0;
 }
 }
returnresult;
 }

}