Maximum Subarray

/*

Maximum Subarray

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.

More practice: If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle.

*/
class Solution {
public:
    int maxSubArray(int A[], int n) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        int pos = 0;
        if(n<=0) return -1;
               
        int result = A[pos];
        while(A[pos]<=0 && pos<n){
          result = max(result, A[pos]);
          pos++;
        }
        if(pos==n) return result;
        result = A[pos];
        int end = pos;
       
        int currSum = result;
       
        pos++;  
        while(pos<n){
          if(A[pos]>=0){
            currSum = currSum + A[pos];
            result = max(result, currSum);
          }
          if(A[pos]<=0){
            if(currSum>=0){
              if ((currSum+A[pos])<0){
                currSum = 0;
              }
              else{
                currSum = currSum+A[pos];
              }
            }
          }
          pos++;
        }
       
        return result;
    }
};