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

• 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.

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