15. Maximum Subarray

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