# Share my sloution On C++

• class Solution {
public:
vector<int> find_max_crossing_sub_array(int A[],int low,int mid,int high)
{
int left_sum = INT_MIN,right_sum = INT_MIN;
int sum=0,max_left=0,max_right=0;
vector<int> temp;
for (int i=mid;i>=low;i--)
{
sum+=A[i];
if (sum>left_sum)
{
left_sum = sum;
max_left=i;
}
}
sum=0;
for (int j=mid+1;j<high+1;j++)
{
sum+=A[j];
if (sum>right_sum)
{
right_sum = sum;
max_right=j;
}

``````}
temp.push_back(max_left);
temp.push_back(max_right);
temp.push_back(left_sum+right_sum);
return temp;
//temp.push_back();
``````

}

vector<int> find_max__sub_array(int A[],int low,int high)
{
vector<int> temp,left_temp,right_temp,cross_temp;
int mid =0;
if(low==high)
{
temp.push_back(low);
temp.push_back(high);
temp.push_back(A[low]);
return temp;

``````}
else
{
mid =(high+low)/2;
left_temp=find_max__sub_array( A,low,mid);
right_temp=find_max__sub_array( A,mid+1,high);
cross_temp=find_max_crossing_sub_array( A,low,mid,high);
if ((left_temp[2]>=right_temp[2])&&(left_temp[2]>=cross_temp[2]))
{
return left_temp;
}
else if ((right_temp[2]>=left_temp[2])&&(right_temp[2]>=cross_temp[2]))
{
return right_temp;
}
else
{
return cross_temp;

}

}
``````

}
int maxSubArray(int A[], int n) {
vector<int> temp,result;
temp= find_max__sub_array(A,0,n-1);

``````    return temp[2];

}
``````

};

It is not simple,but it works. You can refer to the book,《Introduction to Algorithms》，by Cormen, Thomas H. (EDT)/ Leiserson, Charles E./ Rivest, Ronald L./ Stein, Clifford ,my answer comes from that book.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.