Kadane's Algorithm => TC -> O(N)

maxSumKadane.java

public static void maxSumKadane(int arr[]){
  int currSum = 0, maxSum = Integer.MIN_VALUE;
  for(int i=0; i< arr.length; i++) {
    currSum += arr[i];
    if(currSum < 0) currSum = 0;
    maxSum = maxSum>currSum? maxSum:currSum;
  }
  System.out.println(maxSum);
}