DP --- Maximum Subarray Sum in Circular Array

1. For each i, find the maximum subarray sum from 0 to i-1, viz. Si, and the maximum subarray sum from i to      N-1, viz., Ei, the maximum subarray sum for the circular array is maximum of Si+Ei  and compare it with non circular case
 Question:
       how do they know Si+Ei is a continuous subarray?
Answer:
       cause Si is not a subarray sum , it is the partical sum from 0 to anywhere smaller than i

2. Find the minimum subarray sum, since either min or max will cover the cross over of 0 and N-1,

3. Doing non circular finding subarray sum for 2N array, but need to consider the length

For non circular version:
1. Partial sum  - min sum
2. Maximum till i  = max (A[i], max till i ) and maximum sum


Code:

int maxSumNonCirular(const vector &A)
{
    int Mxtil =0;
    int Mx =0;

    for (int i=1; i    {
        Mxtil = max(A[i], A[i]+Mxtil);
        Mx = max(Mx, Mxtil);
    }
    return Mx;
}

int maxCircular(const vector &A)
{
    vector maxBegin;
    int sum = A.front();
    maxBegin.push_back(sum);
    for (int i=1; i    {
        sum+=A[i];
        maxBegin.push_back( max (maxBegin.back(), sum));
    }

    vector maxEnd(A.size());
    sum =0;
    maxEnd.back()=0;
    for (int i=A.size()-2; i>=0; --i)
    {
        sum+=A[i+1];
        maxEnd[i] = max( maxEnd[i+1], sum);
    }

    int cirMax =0;
    for (int i=0; i    {
        cirMax = max(cirMax, maxBegin[i]+maxEnd[i]);
    }
    return cirMax;
}

int maxSubArrayCircular(const vector &A)
{
    return max( maxSumNonCirular(A), maxCircular(A) );
}