public int maxSubArray(int[] A) {
        int max = 0;
        int cur = 0;
        boolean allZero = true;
        int maxNegtive = Integer.MIN_VALUE;
        for (int a : A) {
            cur += a;

            if (cur > max) {
                max = cur;
            }
            if (cur < 0) {
                cur = 0;
            }

            if (a < 0) {
                if (maxNegtive < a) {
                    maxNegtive = a;
                }
            } else {
                allZero = false;
            }
        }
        return allZero ? maxNegtive : max;
    }