class Solution {
     public static int maxSubArray(int[] A) {
         int maxSoFar=A[0], maxEndingHere=A[0];
         for (int i=1;i<A.length;i++){
             maxEndingHere= Math.max(maxEndingHere+A[i],A[i]);
             maxSoFar=Math.max(maxSoFar, maxEndingHere);
         }
         return maxSoFar;
     }


     public static void main(String[] args) {
         Solution solution = new Solution();
         int sol= solution.maxSubArray(new int[]{1, -2, 3, 4});
         System.out.println(sol);
     }
 }