Prefix Sum => TC -> O(N^2)

maxSumSubArr.java

public static void printMaxSumSubArr(int a[]){
    int currSum=0, maxSum=Integer.MIN_VALUE, prefix[] = new int[a.length];
    prefix[0] = a[0];
    for (int i = 1; i < a.length; i++) {
      prefix[i] = prefix[i-1] + a[i];
    }
    for (int i = 0; i < a.length; i++) {
      for (int j = i; j < a.length; j++) {
        currSum = i==0?prefix[j]:prefix[j]-prefix[i-1];
      }
      maxSum = maxSum<currSum ? currSum : maxSum;
    }
    System.out.println(maxSum);
}