# Neat divide and conquer solution

• Here is a divide and conquer approach to solve this problem. Tell me if you have a better way to do it.

``````int maxSubArray(vector<int>& nums, int l, int u) {
if (l == u) return nums[l];
auto m = l + (u - l) / 2;

auto lmax = nums[m];
for (auto i = m, sum = 0; i >= l; --i) {
sum += nums[i];
if (sum > lmax) lmax = sum;
}

auto rmax = nums[m + 1];
for (auto i = m + 1, sum = 0; i <= u; ++i) {
sum += nums[i];
if (sum > rmax) rmax = sum;
}

return max({ maxSubArray(nums, l, m), maxSubArray(nums, m + 1, u), lmax + rmax });
}

int maxSubArray(vector<int>& nums) {
return maxSubArray(nums, 0, nums.size() - 1);
}``````

• That's what I was thinking, but that's O(n lg n) (if I'm not mistaken) and O(lg n) space. So much worse than the iterative solution of O(n) time and O(1) space.
I guess the point of the exercise of divide-conquer is to catch on to the idea of calculating max sub sum from the middle point to the left and to the right.

• Yes. I agree with your opinion.

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