Three Methods: Brute-force, Dynamic Programming & Divide and Conquer


  • 0
    L

    OK...this is a well-known divide and conquer problem, however, before we start to talk about divide and conquer, let's first see another two methods:
    1) Brute-force
    The most naive method, but easy to understand:

    class Solution {
    public:
        int maxSubArray(vector<int>& nums) {
            int len=nums.size();
            int sum=0;
            vector<int> sum_per_round;
            vector<int> max_per_round;
            for(int i=0;i<len;i++){
                sum=nums[i];
                sum_per_round.push_back(sum);
                for(int j=i+1;j<len;j++){
                    sum+=nums[j];
                    sum_per_round.push_back(sum);
                }
                max_per_round.push_back(*max_element(sum_per_round.begin(),sum_per_round.end()));
                sum_per_round.clear();
            }
            return *max_element(max_per_round.begin(),max_per_round.end());
        }
    };
    

    Interestingly, I passed 201/202 cases using these funny codes... but got a sad TLE :-)
    It's not hard to tell that the time complexity of this solution is O(n^2).

    2)Dynamic Programming
    In dynamic programming, the key is to find the dynamic programming equation. To get this equation, we can first study some examples, say, nums[3]={-2,3,3}. In position0, the maximum sub-array is nums[0], i.e. -2. Then what about the maximum sub-array ending with nums[1]? Should it be -2+3 or simply 3? Obviously, it should be 3 because the maximum sub-array ending with nums[0] is less than 0. Similarly, consider the maximum sub-array ending with nums[2], this time we should add 3 to nums[2] because the maximum sub-array ending with nums[1] is greater than 0. Now we see the pattern here:
    Suppose DP[i] is the maximum sub-array ending with nums[i]. If DP[i-1]>0,DP[i]=A[i]+DP[i-1],otherwise DP[i]=A[i].
    Based on this equation, we have the following codes:

    class Solution {
    public:
        int maxSubArray(vector<int>& nums) {
            int len=nums.size();
            int* dp=new int[len];
            int res=dp[0]=nums[0];
            for(int i=1;i<len;i++){
                dp[i]=nums[i]+(dp[i-1]>0?dp[i-1]:0);
                res=max(res,dp[i]);
            }
            delete dp;
            return res;
        }
    };
    

    The time complexity is O(n), much faster than Brute-force.

    3) Divide and Conquer
    Divide and Conquer usually needs three steps:
    a. Divide
    Divide a big problem into sub-problems with smaller size. Traditionally, we usually divide by a half :-)
    b. Conquer
    Recursively solve each sub-problem.
    c. Combine
    Combine the answer we get in Conquer step to form the complete answer.
    In maximum sub-array problem, consider the input array nums[right,left], the maximum sub-array ans[i,j]:
    ①may completely locate in the left part, i.e. nums[left,mid], if left<=i<=j<=mid, where mid=(left+right)/2
    ②may completely locate in the right part, i.e. nums[mid+1,right], if left<=i<=mid<j<=right, where mid=(left+right)/2
    ③may cover the mid, i.e. mid∈[i,j], if left<=i<=mid<j<=right

    We can recursively compute the maximum sub-array of nums[left,mid] and nums[mid+1,right], also, we need a function to compute the maximum sub-array when ans[i,j] covers the mid.
    The following codes are from the famous book CLRS( so... it's not my original work, thanks to this great book :-)

    class Solution {
    public:
        int maxSubArray(vector<int>& nums){
    	    int len=nums.size();
    	    if(len==0)// empty input
    		    return 0;
            else
    		    return find_maximum_subarray(nums,0,len-1);
        }
        
        // the routine finds the max subarr in the left half and right half
        int find_maximum_subarray(vector<int>& nums,int low,int high){
    	    if(low==high)// base case
    		    return nums[low];
    	    else{
    		    int mid=(low+high)/2;// divide
                // conquer
    		    int left_sum=find_maximum_subarray(nums,low,mid);
    		    int right_sum=find_maximum_subarray(nums,mid+1,high);
    		    int cross_sum=find_max_crossing_subarray(nums,low,mid,high);
    		    // combine and return
                return max(max(left_sum,right_sum),cross_sum);
    	    }
        }
        
        // the routine finds the max subarr that crosses mid
        int find_max_crossing_subarray(vector<int>& nums,int low,int mid,int high){
    	    int left_sum=INT_MIN;
    	    int right_sum=INT_MIN;
        	int sum=0;
            // compute the largest sum from low to mid
    	    for(int i=mid;i>=low;i--){
    		    sum+=nums[i];
    		    if(sum>left_sum)
    			    left_sum=sum;
    	    }
    	    sum=0;// reset sum
            // compute the largest sum from mid+1 to high
    	    for(int i=mid+1;i<=high;i++){
    		    sum+=nums[i];
    		    if(sum>right_sum)
    			    right_sum=sum;
            }
    	    return left_sum+right_sum;
        }
    };
    

    Now let's briefly analyze this method's time complexity, the recursion of the method is T(n)=2T(n/2)+Θ(n), by applying the Master Thereom, we know that the time complexity is O(nlgn).
    For more details, please refer to CLRS.


Log in to reply
 

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