int max(int a, int b, int c) {

return std::max(std::max(a,b),c);

}

int maxSubArrayCross(int A[], int l, int m, int h) {

int sum = 0;

int leftSum = INT_MIN;

for (int i = m; i >=l; --i) {

sum += A[i];

if (sum > leftSum) leftSum = sum;

}

sum =0;

int rightSum = INT_MIN;

for (int i = m+1; i <=h; ++i) {

sum += A[i];

if (sum > rightSum) rightSum = sum;

}

return leftSum + rightSum;

}

int maxSubArrayUtil(int A[], int l, int h){

if (l ==h) return A[l];

int m = l + (h -l) /2;

return max(maxSubArrayUtil(A, l, m),

maxSubArrayUtil(A, m+1, h),

maxSubArrayCross(A, l, m, h));

}

int maxSubArray(int A[], int n) {

return maxSubArrayUtil(A, 0, n-1);

}

int maxSubArray(int A[], int n) {

int sum = 0;

int maxSum = INT_MIN;

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

sum = std::max(sum + A[i], A[i]);

maxSum = std::max(sum, maxSum);

}

return maxSum;

}