public class ArraySum {

    public static void main(String[] args) {
        int[] inputArray = {-2,1,-3,4,-1,2,1,-5,4};
        int [] result = subArraySum(inputArray);
        System.out.println("Max sum: " + result[0] + ", maxSumLowerBound: " + result[1] + ", maxSumHigherBound: " + result[2]);
    }

    private static int[] subArraySum(int[] inputArray) {
        int arraylength = inputArray.length;
        int maxSum = Integer.MIN_VALUE;
        int maxSumLowerBound = -1;
        int maxSumHigherBound = -1;

        for (int i = 0; i < arraylength; i++) {
            int sum = 0;
            for (int j = i; j < arraylength; j++) {
                sum += inputArray[j];
                if (sum > maxSum) {
                    System.out.println("old sum: " + maxSum + ", new sum: " + sum + ", maxSumLowerBound: " + i + " , maxSumHigherBound: " + j);
                    maxSum = sum;
                    maxSumLowerBound = i;
                    maxSumHigherBound = j;
                }
            }
        }

        return new int[]{maxSum, maxSumLowerBound, maxSumHigherBound};
    }


}