Hello whatsup guys, Anuj here and welcome to the DSA 1 course and today we are going to talk about arrays Today we will move ahead in arrays, and discuss one more important question in array that is maximum sum subarray And there is an important algorithm in this, which is Kadane's Algorithm This question and this algorithm is already been asked in many big companies, like Paypal, Amazon, Microsoft have asked them There is an important concept in this, and the Kadane's Algorithm is very important We are going to understand this, what is the question? Question is maximum sum subarray, means you are given an array and you have to find a small part of that array, a subarray Whose sum is maximum Suppose this is your array, and it has both positive and negative element, from this you have to find a small subarray, whose sum is maximum So over here if we see, we will get this one, 4,6,-3 and 4, sum of these is the maximum, we will add and see, it will be 11 Basically, this is our question and there are multiple techniques to solve this, already you might be getting multiple techniques in your brains But the most efficient technique is Kadane's algorithm We are going to see it First of all brute force solution, to do any question brute force solution should come into your mind first What could be the brute force for this? I am able to see over here that I have a sub array, and whenever there is a question of sub array So to find the sub array, your brute force should be to find all the sub array How many arrays can be formed into this, I will see all the subarrays And after that I will calculate the sum of all And the subarray with maximum sum, will be my answer In this array if want to traverse all the sub arrays then one technique can be we will use 2 for loops What it will be? we will start from here, so first subarray will be – 5 to 5 Next will be -5 to 4, next will be -5 to 6, -5 to -3, -5 to 4, and -5 to -1 So, we have seen all the sub array starting from -5 Now, we will see sub array that are starting form 4 4 to 4, 4 to 6, 4 to -3, 4 to 4, 4 to -4 So now we have seen all the sub array starting from 4 Now, we will jump to 6 Now we see all the subarrays starting from 6 6 to 6, 6 to -3, we will move on like this We will see all the sub arrays like this And our answer will be this sub array 4 to 4, fine And we will return that, code is going to be very simple Basically, it will be like this, first for(int i=0; i<n,i++){ and one more nested for loop will be in it for( int j=i; j<n; j++){ And by doing like this we can traverse all the subarrays By doing like this, we can go through all the subarrays We will go on calculating sum, int sum, and we will make maxsum=-infinity And when ever we will feel that this sum is greater than maxsum, then we will put it into maxsum And by doing so, we will finally return maxsum, this is one way But over here can you see, that the time complexity is O(n2), an interviewer will say this is not a good time complexity And try to Optimize this So you will try to optimize this, if you remember the last question What we had done into that? We had sorted the array, but I had told you that you should sort only when order does not matter Over here as soon as you will sort this, your order will be changed Now your array will be -3,-5,-1, 4,4,6 it will be like this So, you had to find subarray, but you changed the order so now there is no question only So, now you cannot find the subarray, so sorting is out of picture, we cannot do sorting in this Sorting cannot be done, so what ever you were thinking related to sorting, binary search and all, now leave all that, so it will not be n(log n) So this means, over here we can use space, we can try to solve using space So think it once, can this thing be done using space? Or you have to think of something else Think, so if you people might have thought, there is no use of using space also Because even if you will use space, you will have to see all the subarrays, so the time complexity will be O(n2) So by using space also this will not be solved Because we will have to see all the sub array, so what is the benefit We will not use space, but it is still said that we can optimize this, then we will have to think one more logic, with which we can solve this question What was the question, question was maximum sum subarray Means, you have to find such subarray, whose sum is greatest Suppose, we will start from a smaller problem First of all in the array we have just 1, so the answer is 1 Suppose next we have 2 in the array, then the answer is 1+2=3 Suppose array contains 1,2,3, so answer will be 1+2+3=6 So can you understand 1 thing from here, that if all the elements are positive then we can do sum of all and that is our answer If you keep on bringing more positive elements, so we will just do sum of all and that only will be our answer ok, but the problem comes when we add a negative element in this Suppose, after 1, I have -2, then we will have to think with negative elements So now there are 2 elements in this, 1 and -2 So will I include -2, no I will not include So my answer will be 1 Fine, 1 is the answer Now suppose, we after 1, -2,we get one more 1 so now what will be the answer, so now can I try to make the whole sub array Again it is subarray and not subsequence which means you have to include all the elements So can we get answer from these 3?, we will get the answer 0 And if I use any one element, any 1, then my answer will be 1 So I can say its sum maximum subarray is 1 Either take this or this Means, I have not included this one Ok, if I put 2 over here, then what will happen? So -2 +2=0, an this is 1 So if I try to include everything it will be 1 If I skip this 1, then my answer will be 2 So, from here only we can see one more thing, that if I do 3,4 or 5 over here, suppose I am doing 3 Then I see that there is benefit in keeping this 3, because -2 is reducing the value of 1 due to this -2 I am not able to include this 1 This means, after this even if there is something else, suppose after 3 there is 2 or 1, suppose anything comes after 3 I know that if I want to include 3 then I will not include -2 and 1 Because due to -2 the value of 1 has reduced If I try to include this part then I am taking -1, 1 + -2=-1 This part is giving me -1 So why will I include this part? So over here we should think one thing that if we are going like this, we are going one by one, because we are told we have to solve in O(n) So we are moving one by one in this, then we don't have to take this part, if its total sum is negative If any part, any subarray's total sum is negative, then there is no benefit in including that part If we can see the sum of this part is -1, then there is no benefit in including it Because it will reduce overall sum This part will always reduce the overall sum, so we will not include this Now we will say, your work is done over here only Maximum you can get is 1, other then that you cannot bring anything, so this part is finished Now we can start the same story from here Same story will start from here Now we took 3+2=5, suppose we added an element -6, then we added 4 3+2=5, now 5+(-6)=-1, so this part is giving me -1 And now I will come here at 4, should I include this whole part into this where I am getting 3 and 2 I will say no, I am getting 3 and 2, but over here -6 is also there, I am getting overall a negative number, so it will reduce my sum At present I am getting 4 from here, but if I will include everything from here then I will get 4 + -1=3 There is no benefit so, again negative element is discarded, you said whatever maximum I can get from this part is 3+2=5 So, I will just take 5 from here and do my work, I will move ahead Now you can start to do the processing with 4 So in this way you can move ahead What's the basic trick? trick is you keep on moving ahead but as you see the sum is negative, overall sum is negative You discard that part over there only And start the story from next element Start the story again from next element Now again over here we have 4, it is possibile that there can be anything in it,it can be 1000, 100 anthing can be over here Even -200, so same story will start from here also Now we got, 4+100=104, After 104 it is -200, so 104 is our answer Why 104 will be the anser? Why are you not inculdeing this part in 104? Because if we will include this part then we will get, 3+2=5 Now again we have 4 over here, anything can be after this 1000,100 or -200 So, a new but same story will start from here Again we got 4+100=104, then -200, so 104 is our answer Why 104 is the answer? Why are we not including this part? Because if we will include this part then we will get 3+2=5 + -6=-1 So if we will try to include this part then we will get 103 instead of 104 There is no benefit in taking 103, we have benefit by taking 104 So we will discard this part Because the overall sum is negative So this is our Kadane's Algorithm, it is based on this thing only This algorithm which I have told you over here, is Kadane's Algorithm and I will code it once So you will understand it clearly This basically will get solved in O(n), because you are traversing only 1 time in whole array You have not used any space, so this will bring from O(n2) to O(n) This is quite huge optimization to bring from O(n2) to O(n) So this is quite good algorithm I think you might have understood also I will code this and show it to you Ok so I have coded the same thing over here, this maxSumSubArray function which is taking an array And its works is to return the maxsum being calculated from subarray So I have made 2 variables, maxsum and cursum, which I had told you in the same logic We will start here from, 0 And we will keep on moving forward, so cursum=cursum+a[i], cursum was initially 0, so 0+a[i] Means the current element, I am taking this example [5,-4,-2,6,-1], so cursum =5 So cursum=5 and maxsum was 0 So we will check if cursum>maxsum, yes 5>0, then maxsum=cursum, so maxsum=5 And we will check if our cursum is negative? no our cursum is not negative, we will go in next iteration We will add next element in cursum, so 5 + -4= 1, so cursum=1 We will check if cursum>maxsum, no, so we need not do anything, and cursum is also not negative, so we not do anything, we will go on next element We will add next element in cursum, samething we will add in current So -2 +1=-1, is this greater than maxsum, is this negative?yes this is negative So if this is negative, then cursum=0, this part is giving overall negative sum so we will discard this part And because this is coming negative, so cursum=0, so we are not going to get answer from this part, maximum which can come from this part is 5 So we have kept maximum with us but contribution of this part was till here only, we are not going to consider this part any further We will move ahead, next is 6, we will add 6 in cursum, so cursum=6 So 6>5, so we will come here, is cursum>maxsum? yes, 6>5, so maxsum=6, and it is not negative so we will move forward,and we will see -1 over here If we will include -1, then it will be 5, is this greater than maxsum?no.
So in the end our maxsum will be 6, loop will be finished We will return maxsum. we finally returned maxsum, I hope you all can see the last line So in this way, Kadane's Algorithm works. This algorithm converts this solution into O(n) One more thing, if all the elements are negative then you will have to solve this problem in a bit different way I am giving you all this as task , that if all the elements are negative, then try to find the issue in this solution, if all the elements are negative then it will not give the answer And try to correct it, it is not that big, if all the elements are negative then it will be solved in a different way So you have do some tweaks in this and you will get it So with this I will give you the link in description, so you can go and see there With this only I will end this video.
In this we have seen Kadane's algorithm Which is a very important algorithm Like this video, share and subscribe to the channel And I will meet you in next video bye bye!.