Finding Maximum Sum SubArray using Divide and Conquer Approach.

Subscribe for more DSA videos!

**Resources for Competitive Programming/Coding Interviews:
**

Edit: I made a mistake for the subarray on the left [-2,-5,6,-2]: The LSS=-2 RSS=6 and CSS=1.
For CSS{ mid+1=6 ,to the right max=6},{mid=-5 ,on the left max=-5} so CSS=(6-5)=1 Not -1.
In this video I am going to show how to use divide and conquer to find the maximum value of sum of a contiguous subarray.

[sareek]

for css if anybody is confused, have a look at calculating CSS for below,
-2, -5, 6, -2, -3, 1, 5, -6
divide into 2 we get,
-2, -5, 6, -2
for left part, go from right to left,
(-2) + (6) = 4
4 + (-5) = -1
-1 + (-2) = -3
Now maximum of all these results is 4,
similarly for right part i.e. -3, 1, 5, -6 do same go from left to right starting from middle(i.e. adding two consecutive elements, we get,
(-3) + 1 = -2
-2 + (5) = 3
3 + (-6) = -3
what is the maximum of these three ?? it is 3, right?
so from left we have maximum value 4 and from right 3, add these two to get CSS value,
that is 7

[shreemantolahiri]

At @5:11 the CSS should be +1, because:

from left, A=-5
from right, B=6 not 6-2=4(wrong)

so A+B=-5+6=1

CSS must be +1. Spent 20 mins thinking was I wrong, or @AshishKumar.
Nevertheless, ans will be same. Please correct me iif I'm wrong.
Hope this helps someone like me xD

[devanshmesson]

If Anyone is still confused regarding explanation of CSS i am writing here :

Let A = Maximum continuous sum in left part of the array starting from mid element.
Let B = Maximum continuous sum in right part of the array starting from mid+1 'th element.
let low = first element of the array
let high= last element of the array.
So, CSS for an array is calculated as: A + B

Q - why are we starting from the mid'th element ?
Ans - because CSS means the centre of the array which eventually means that some elements of subarray having maximum sum are in the left part of array and some elements of subarray having maximum sum are in the right part of the array.

Suppose, If we compute maximum continuous sum in the order from low to mid (or high to mid+1) then suppose if first element is the subarray having maximum sum, then this method is wrong because this subarray will not be linked to the subarray having maximum sum in the right part of the array.

In short we have to link both maximum subarray in left part as well as right part to make it crossing sum subarray(CSS).

For example array is 7, -6, 5, 4, -2, 1
(Considering 0 based indexing)

index of mid element = 2
value of mid element = 5

A will computed as :
Keep adding every element one by one starting from mid element :and keep track of the maximum sum

Sum=0
Sum= sum + 5, , sum=5, A = 5
Sum = Sum + (-6), sum=-1, A =5
Sum = Sum + 7, sum=6, A = 6
Subarray having maximum continuous sum in left part of the array : [7, -6, 5]

B will computed as :
Keep adding every element one by one starting from mid element :and keep track of the maximum sum

Sum=0
Sum= sum + 4, , sum=4, B = 4
Sum = Sum + (-2), sum=2, B =4
Sum = Sum + 7, sum=3, B = 4
Subarray having maximum continuous sum in right part of the array : [4]

SO, CSS for the array [7, -6, 5, 4, -2, 1] = [7, -6, 5, 4]

Note : if you start the counting of the sum from the right most part of the array (r) then value of B will be less.
Demonstration of the above argument:

Sum=0
Sum= sum + 1, , sum=1, B = 1
Sum = Sum + (-2), sum=-1, B =1
Sum = Sum + 4, sum=3, B = 3



So, this proves that CSS should be calculated from the mid element.

[ikhycyx]

wow
this conceptual understanding is what i was looking for
this cleared a lot of my clouds!!

[timbenton]

Thanks for diagramming this as a tree! I was looking for an explanation that helped me understand how the left and right recursive calls worked since only the crossing function iterates through the array. This explained it perfectly!

[parthsalat]

Best explanation for Finding Maximum Sum SubArray using Divide and Conquer Approach. Thanks.

[hiteshgupta]

bhaiya bohot acha saamjaya aapne thank you.

[alexanderlin]

wow... this problem really blows my mind, feel that trying to use a way more complicated solution to save not much time. (compare to the O(n) solution.)

[light-qnjb]

Thank you it took me all day yesterday to figure out how it get the max sum from left and right with just the max number but with the graph you draw I can see it now the when they reach the bottom out the crossing sum will do all the summation

[Luna-vkxy]

At 5:12 shouldn't css be 1? Going right from mid point would give max sum as 6 not 4. And going left would give -5 not -7. 6-5 would be 1? Correct me if I'm understanding this wrong

[pragyanbansal]

🎯 Key Takeaways for quick navigation:

00:00 *📚 The problem discussed is finding the maximum sum subarray from a given array of integers.*
01:07 *🔍 Divide and conquer approach is suggested as a more efficient solution compared to the naive approach of using nested loops.*
03:50 *🔄 For finding the maximum sum subarray, the array is divided into left, right, and crossing subarrays, and the maximum of these is returned recursively.*
06:45 *📊 Calculation of the crossing subarray sum involves finding the maximum sum towards the left and right from the midpoint and summing them up.*
10:15 *🧮 By comparing the maximum sum subarrays from left, right, and crossing, the overall maximum sum subarray is determined algorithmically.*

Made with HARPA AI

[allentigga]

I understood the algorithm
but I am confused about the inution to this approach.

[devanshmesson]

Thank you so much.
Best explanation ever!

[kushalljain]

what about odd number of elements, i am getting confused over that

[varunkiran]

What if there are an odd no of elements?

[josephferraro]

How can you code this recursively? Since we are doing CSS differently in different cases I cannot see how to do this. We originally do CSS as the sum of the left and right partitions, and then somehow in the last step we do CSS where we find the max sum of the array in total. If we could do that the whole time then that would just be the O(n) solution and not the divide and conquer. As in, the final way u find CSS is O(n) and this also finds the max sum subarray so you are adding extra steps to the O(n) to make it divide and conquer. But I don't see how this is useful if that is the way to find CSS in the final iteration, there must be a different way to find CSS in the last step.

What I'm meaning to say here is that you took the O(n) solution - which was the very last step where you found CSS. And then on top of it you did a part of a divide and conquer solution. So I don't understand what the point of the algorithm is if we must use the O(n) solution as a part of the divide and conquer solution.

[AnshKaurms]

@ 5 : 11 you confused me, please tell it clearly.

[sharwansinghrathore]

u made me confuse in css part after returning

[sfhibye]

how css is being -1 in 5.18 minutes. can u help

[anuragdeol]

Hey, can anyone please confirm that divide and conquer solution is giving TLE for a very large test case? Or is it just me and have done some mistake in my code? (Leetcode problem - 53. Maximum Subarray)