A Divide and conquer algorithm


  • 0
    B
    int maxSubarray(vector<int> & subArray, int I, int J)
    {
    	if (J < I)
    	{
    		return 0;
    	}
    	if (I == J)
    	{
    		return subArray[I];
    	}
    	int sum = 0;
    	int M = (I + J) / 2;
    	int maxToLeft = subArray[M];
    	int maxToRight = subArray[M + 1];
    	for (int i = M; i >= I; i--)
    	{
    		sum += subArray[i];
    		if (sum > maxToLeft)
    		{
    			maxToLeft = sum;
    		}
    	}
    	sum = 0;
    	for (int i = M+1; i	 <= J; i++)
    	{
    		sum += subArray[i];
    		if (sum > maxToRight)
    		{
    			maxToRight = sum;
    		}
    	}
    	int sumCross = maxToLeft + maxToRight;
    	int maxofLeft = maxSubarray(subArray, I, M);
    	int maxofRight = maxSubarray(subArray, M + 1, J);
    	return max(max(sumCross, maxofLeft) , maxofRight);
    
    
    }
    

    REFERENCE: http://dl.acm.org/citation.cfm?id=381162


Log in to reply
 

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