# Sharing my divide and conquer solution using C++

• ``````int maxSubArray(int A[], int n) {
return divideAndConquer(A, 0, n - 1);
}
int divideAndConquer(int A[], int left, int right){
if(left == right){
return A[left];
}
if(left > right){
return INT_MIN;
}
int mid = left + (right - left) / 2;
int maxLeft = 0;
int sum = 0;
for(int i = mid - 1; i >= left; i--){
sum += A[i];
maxLeft = max(maxLeft, sum);
}
int maxRight = 0;
sum = 0;
for(int i = mid + 1; i <= right; i++){
sum += A[i];
maxRight = max(maxRight, sum);
}
int maxSumWithMid = maxLeft + A[mid] + maxRight;
return max(maxSumWithMid, max(divideAndConquer(A, left, mid - 1), divideAndConquer(A, mid + 1, right)));
}``````

• Sharing my java divide and conquer code

``````   public class Solution {
public int maxSubArray(int[] A) {
return helper(A, 0, A.length);
}

public int helper(int[] A, int start, int end){
if(start==end-1) return A[start];
int middle = (start + end) / 2;
int leftSub = helper(A, start, middle);
int rightSub = helper(A, middle, end);
int i,leftcut=-1,rightcut=-1,leftsum=0,rightsum=0,leftmax=-Integer.MAX_VALUE,rightmax=-Integer.MAX_VALUE;
for(i=middle;i<end;i++){
rightsum += A[i];
if(rightsum>=0 && rightsum>rightmax){
rightmax = rightsum;
rightcut = i;
}
}
for(i=middle-1;i>=start;i--){
leftsum += A[i];
if(leftsum>=0 && leftsum>leftmax){
leftmax = leftsum;
leftcut = i;
}
}

int sub;
if(leftSub>rightSub){
sub = leftSub;
}
else{
sub = rightSub;
}
if(leftcut==-1 || rightcut==-1){
return sub;
}
else{
if(sub>leftmax+rightmax){
return sub;
}
else{
return leftmax + rightmax;
}
}
}
}``````

• Does divide n conquer act like a divide n conquer style dp?

• I think the run time is O(n) + O(n/2) + O(n/4)...+O(1), it's d&c, but not more subtle.

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