Can divide-and-conquer solution be acccepted?


  • 0
    T

    I've solve this problem using divide-and-conquer, which refer to the implementation of the one in

    'Bentley, Jon (1984), "Programming pearls: algorithm design techniques", Communications of the ACM 27 (9): 865–873, doi:10.1145/358234.381162'

    Below is the psedocode of his algorithm in the paper:

    recursive function MaxSum(L, U) 
    if L > U then /* Zero-element vector */ 
    	return 0.0 
    if L = U then /* One-element vector */ 
    	return max(0.0, X[L] ) 
    
    M := (L + U)/2 /* A is X[L..M] , B is X[M + 1..U] */ 
    
    /* Find max crossing to left */ 
    Sum := 0.0; MaxToLeft := 0.0 
    for I := M downto L do 
    	Sum := Sum + X[I] 
    	MaxToLeft := max(MaxToLeft, Sum) 
    
    /* Find max crossing to right */ 
    Sum := 0.0; MaxToRight := 0.0 
    for I := M + I to U do 
    	Sum := Sum + X[I] 
    	MaxToRight := max(MaxToRight, Sum) 
    
    MaxCrossing := MaxToLeft + MaxToRight 
    MaxInA := MaxSum(L, M) 
    MaxInB := MaxSum(M + I, U) 
    
    return max(MaxCrossing, MaxInA, MaxInB) 
    

    And here is my implementation:

    public:
    int maxSubArray(int A[], int n) {
        return getMax(A, 0, n-1);
    }
    private:
    int getMax(int A[], int begin, int end){
        if(begin > end){
            return 0;
        }
        
        if(begin == end){
            ////return max(0, A[begin]);
            return A[begin];
        }
        
        //left is [begin..mid], right is [mid+1..end]
        int mid = (begin + end) / 2;
        
        //find max crossing to left
        int sum = 0;
        ////int maxToLeft = 0;
        int maxToLeft = INT_MIN;
        ////for(int i=mid; i>=0; i--){
        for(int i=mid; i>=begin; i--){
            sum += A[i];
            maxToLeft = max(maxToLeft, sum);
        }
        
        //find max crossing to right
        sum = 0;
        ////int maxToRight = 0;
        int maxToRight = INT_MIN;
        for(int i=mid+1; i<=end; i++){
            sum += A[i];
            maxToRight = max(maxToRight, sum);
        }
        
        int maxInLeft = getMax(A, begin, mid);
        int maxInRight = getMax(A, mid+1, end);
        
        return max(max(maxInLeft, maxInRight), maxToLeft+maxToRight);
    }
    

    I get Timelimt Exceeded error. Is there a better solution for divide-and-coquer?


  • 1
    H

    i used the following code and get accepted.

    public class Solution {
       	//dive and conquer begin
    	public  int maxSubArray(int[] A) {
    		int max = 0;
    		max = maxSubInOneSection(0,A.length-1,A);
    		return max;
    	}
    	
    	public  int maxSubCrossing (int l,int r,int mid,int[] a) {
    		int suml = 0,maxl = Integer.MIN_VALUE;
    		for (int i = mid; i >= l; i--) {
    			suml += a[i];
    			if(suml>maxl)
    				maxl = suml;
    		}
    		int sumr = 0, maxr = Integer.MIN_VALUE;
    		for (int i = mid +1; i <= r; i++) {
    			sumr += a[i];
    			if(sumr>maxr)
    				maxr = sumr;
    		}
    		return maxl+maxr;
    	}
    	
    	
    	
    	public  int maxSubInOneSection (int l,int r, int[] a) {
    		if(l==r) {
    			return a[l];
    		}
    		
    		int mid = (l+r)/2,lmax=0,rmax=0,crossMax=0;
    		int max = Integer.MIN_VALUE;
    		lmax = maxSubInOneSection(l,mid,a);
    		rmax = maxSubInOneSection(mid+1,r,a);
    		crossMax = maxSubCrossing(l,r,mid,a);
    		if(lmax>rmax){
    			max = lmax;
    		}else {
    		    max = rmax;
    		}
    		if(crossMax >max){
    			max = crossMax;
    		}
    		return max;
    	}
    	//dive and conquer end
    }

  • -2
    S

    The running time of your code follows:

    T(n) = 2T(n/2) + kn

    This is the same as the complexity of quicksort or mergesort. According to Master's Theorem, the complexity of your code should be O(nlogn).

    Instead, this problem can be solved in O(n) with Dynamic Programming.


  • 0
    T

    Thanks for answers below, help me to find the error in my code.
    I've fixed my code, the mistakes are labeled with ////


  • 0
    A

    Your function maxSubCrossing took O(n) for every calls and you are making log(n) calls so its O(nlogn). Divide and conquer supposed to do it in O(logn) because O(n) solution is trivial


  • 0
    A
        max_sum = A[0]
        temp_sum = 0
        for element in A:
            temp_sum += element
            if temp_sum > max_sum:
                max_sum = temp_sum
            if temp_sum < 0:
                temp_sum = 0
        return max_sum

Log in to reply
 

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