/**
 *  non-empty array A consisting of N integers is given. A pair of integers (P, Q), 
 *  such that 0 ≤ P ≤ Q < N, is called a slice of array A. The sum of a slice (P, Q) is the total of A[P] + A[P+1] + ... + A[Q].
 *
 * Write a function:
 *
 * class Solution { public int solution(int[] A); }
 *
 * that, given an array A consisting of N integers, returns the maximum sum of any slice of A.
 *
 * For example, given array A such that:
 *
 * A[0] = 3  A[1] = 2  A[2] = -6
 * A[3] = 4  A[4] = 0
 * the function should return 5 because:
 *
 * (3, 4) is a slice of A that has sum 4,
 * (2, 2) is a slice of A that has sum −6,
 * (0, 1) is a slice of A that has sum 5,
 * no other slice of A has sum greater than (0, 1).
 */
public class MaxSliceSum {
    public int solution(int[] arr) {
        if (arr == null || arr.length == 0) return 0;
        long msum = arr[0], sum = arr[0];

        for (int i = 1; i < arr.length; i++) {
            if (arr[i] > sum && sum < 0) {
                sum = arr[i];
            } else {
                sum += arr[i];
            }
            if (msum <= sum) {
                msum = sum;
            }
        }
        return (int) msum;
    }

    public static void main(String... args) {
        System.out.println(new MaxSliceSum().solution(new int[]{-1, 3, 7, -6, 14, 0}));
        System.out.println(new MaxSliceSum().solution(new int[]{-10}));
        System.out.println(new MaxSliceSum().solution(new int[]{-10, -9, -8, -7, -1}));
    }
}