Share my sloution On C++


  • 0
    J

    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.


Log in to reply
 

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