package dynamicProgramming;

public class MaxSubArraySum {

    public static void main(String []args){
        int [] test = {1,2,-3,-4,-5,6,3,-10};
        System.out.println(maxSum(test));

    }

    public static int maxSum(int [] array){
        int endSofar =Integer.MIN_VALUE;
        int endHere = Integer.MIN_VALUE;
        for(int i =0 ;i < array.length ;i++){
            endHere = Math.max(0, endHere+array[i]);
            endSofar = Math.max(endSofar, endHere);
        }
        return endSofar;
    }
}