package com.companyname.packagename;

import static java.lang.Math.max;

/**
 * Cracking the Coding Interview question 16.17 "Contiguous Sequence" on page 183.
 */
public class ContiguousSequence
{
    public static long maxSubArraySum(int[] arr)
    {
        if (arr == null)
            throw new NullPointerException();
        if (arr.length <= 0)
            throw new IllegalArgumentException("array cannot be empty");

        long maxSubarraySum = arr[0];
        long maxSuffixSum = arr[0];

        for (int i = 1; i < arr.length; i++) {
            maxSuffixSum = max(maxSuffixSum + arr[i], arr[i]);
            maxSubarraySum = max(maxSubarraySum, maxSuffixSum);
        }

        return maxSubarraySum;
    }
}