Maximum Sub-array Sum Using Kandane's Algorithm

Problem link:
                     [https://www.interviewbit.com/problems/max-sum-contiguous-subarray/]

Statement:

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

For 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.

For this problem, return the maximum sum.

Catagory: Kandane's Algorithm, Divide and conquer, Bruteforce

Explanation: This problem can be solved either O(n^3),O(n^2) ,O(nlogn) or O(n). Kandane's algorithm is the O(n) solution and i find it so simple and fascinating.

Study Material: codeschool tutorial

                         [https://www.youtube.com/watch?v=ohHWQf1HDfU&feature=youtu.be]

Code:

int Solution::maxSubArray(const vector<int> &A) {

details

    int n=A.size(),s=0,a=INT_MIN,m=INT_MIN;

    for(int i=0; i<n; i++)

    {

        if(s+A[i]>0)

        s+=A[i];

        else

        {

        

        a=max(a,A[i]+s);

            

        s=0;

        continue;

        }

        

        a=max(a,s);

    }

   

    return a;

    

}