Hi Guys, you can now book a 1:1 call with me on topmate.io/ashishcode for placement guidance and more at a very affordable price. Use code KZfaq30 for 30% off! (Only for first 15 Users)

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 .....................,-3,1,5,-6 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

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

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.

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!

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

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

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

bhaiya bohot acha saamjaya aapne thank you.

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

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

nice one bro!

🎯 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

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.

Thanks, very helpful!

Thankyou for teaching this algorithm

very good approach!!!

What if there are an odd no of elements?

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

Thank you so much. Best explanation ever!

Thank you very much 💫

this is amazing

good one buddy

This is awesome

Nice teaching... 👏🏻👏🏻

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

u made me confuse in css part after returning

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)

css explanation was lil confusing...

are u correct my bro

Thenx

please stop confusing us man.

first approach will be n^3

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

You can easily calculate the CSS part for -2 -5 6 -2 here we divide from 6 as the array was[0=>-2 1=>-5 {2=>6} 3=>-2] So, from 6 to left we will sum, and after 6 to right we will sum too. From 6 to left we have -2 - 5 6 Here, 6+(-5) = 1 As the value is decreasing from 6 so we will avoid the sum as we didn't sum so, from 6 to left we have only the value 6 Now, after 6 to right, we will sum too. as we don't have any more elements except -2 so, after 6 to right, we have only the value -2. so, sum for CSS is =6 to left value +after 6 to right value = 6 + (-2) = 4 it is(4) our CSS for -2 - 5 6 -2 this array LSS = -2 RSS = 6 CSS = 4 As the 6 is the max value so we will return 6 for -2 - 5 6 -2 -3 1 5 -6 this array and it will be LSS for this array.... *********************** Same way for -3 1 5 -6 here we divide from 1 as the array was[0=>-3 {1=>1} 2=>5 3=>-6] from 1 to left we have -3 1 sum, -3+1=-2 value decreasing so avoid sum from 1 to left we got (1) after 1 to right we have 5 -6 sum, 5+(-6) =1 value decreasing so avoid sum after 1 to right, we got(5) So, sum the left(1) and right(5) value CSS = 1+5 = 6 we had, RSS = 1 LSS = 5 Max 6 As the 6 is the greater value so we will return 6 for -2 -5 6 -2 -3 1 5 -6 this array and it will be RSS for this array.... **************************** -2 -5 6 -2 -3 1 5 -6 this array LSS = 6 RSS = 6 For CSS from -2 to left -2+6 = 4 increasing value so continue the sum 4+(-5)=1 value decreasing so avoid sum...x left side (4) Right side after -2 to right -3 1 5 -6 -3+1=-2 increasing value so continue the sum -2+5=3 increasing value so continue the sum 3+(-6)=-3 value decreasing so avoid sum...x Right side(3).... sum for CSS = 4+3=7 So,CSS has max value & will be Maximum Sum SubArray = 7 array will be 6 -2 -3 1 5 l|||||ll|||||ll|||||ll|||||l

How does the css become - 1(at 5.11)?

5:04 what are you saying bro . please make viewers understand . not yourself

your video's volume is not good, its low.

Confusing!!

I think he made a mistake 5:01, shouldnt css = 1 here

You are using HP laptop 🤔

goat

Arigato

it was too confusing

You confused me

un alupa pathavan

jab videos me thoda loud bolne kya effort nahi kar sakthy thy tho video upload krne ka effort kyu kr rhe ho kam se klam thoda loud thobolo ab haar baar zaroori nahi ki viewer ke pass headphone ho