Max Sum Contiguous Subarray

Problem: Find the contiguous subarray within an array (containing at least one number) which has the largest sum.

Example:

Given the array [-2,1,-3,4,-1,2,1,-5,4],
the contiguous subarray [4,-1,2,1] has the largest sum = 6.

Solution:

Since the problem demands that the subarray should contain at least one element, in the base case where  size of given array is one, then return this value.

The idea that if we have to find the max sum of contiguous subarray till index i, we calculate the max sum till index i-1 and add the array value at index i in this. If the new max value is greater than the array value at index i we continue same process with i+1 index else we replace the max value till index i with A[i].
Our final answer is the maximum of all the intermediate max sum values obtained. 



C++ Code:

int maxSubArray(const vector &A) {
    int s = A.size();
    int ans = A[0], m = 0;
    if(s==1)
        return A[0];
    for(int i = 0; i < s; i++)
    {

        m = m + A[i];
        if(m < A[i])
            m = A[i];
        if(ans < m)
            ans = m;
    }
    return ans;
}