Hi, everyone, welcome back.
So in this video, we are going to discuss one very important question, which is the maximum Zebedee.
So the question is very simple.
You are given Manetti, this is 180 fine.
What do you need to do in order to find out?
One contiguous.
Sabeti Not one year to find out the contiguous Sabari which has the maximum sum.
So in this area, if we talk or let's talk about this area so the Sabeti can be five, this can be five
and for the next Sabeti can be five for minus one.
Next subarea can be five for minus one seven.
Knecht Sabeti can be five for minus one seven eight eight.
And then the next Cybertech and before then it can be four minus one, then it can be four minus one
seven, then it can be four minus one seven eight.
Then next can be basically minus one, then it can be minus one seven, then it can be minus one seven,
eight and so on.
You got my point.
So we have multiple samaris multiple contiguous Cibeles.
So out of all these possible contiguous savary, what do we need to do?
We need to find out the sum of all other matters and it would take the maximum.
So in this case, it is saying the maximum sum is twenty three.
So how make some some can be grown bedri in this savary if we will pick this Sabari.
If we will fix this better than the sum of all the elements came out of it or the 380 is the largest
sum in this case, there will be many samaris, but we are only interested in that.
Sabeti, which has the maximum sum and we need to return the maximum sum.
So this subarea has the maximum sum, which is six, right.
This one.
So we need to get it done this summer.
Now, how we can solve this question, so first approach is very simple like this, right?
What do you do?
You tend to lose in this case, you will run to loop.
So in the outer loop, you will fix the element.
For example, I will fix element five and in the inner loop, you will I over all the elements and you
will add the values.
Right.
You will add values and then you will maintain one variable, which is the maximum sum.
And if the sum of the error, if the sum of the SABERA is greater than the maximum sum, you update
the maximum.
So in this case, when you consider each and every SABERA and find out the sum your time complexity
will be, you will be using two loops.
So time complexity for considering all the subsidies will be big off and square and space will be big.
Often you will be creating very few variables.
So this is the time and the space complexity.
Right.
But what we want we want to solve this problem in big off in time and constraint space.
So this is this can be achieved with the help of an algorithm, which is Koran's algorithm.
So Caden's algorithm helps us in finding out the maximum some sabari and how cadenced algorithm works.
So let me explain to you, so what happens in condensed algorithm is basically as soon as you son your
current sum becomes negative, you will make your current sum to be zero.
This is what this algorithm does.
If the current sum is negative, then Makarand equals to zero.
So let's use credential Vadum on this and how it will work.
So initially my maximum sum, what is my maximum sum.
So make some sum essentially the same minus infinity rate so it will be delighted with the idea.
Let's do it.
So minus two.
So what do do.
Current term is initially zero, and you will add the current element of the added to the current,
so current sum will become minus two rate, you will add minus two to zero.
So current sum is minus two.
Then we will compare.
So minus two and infinity, which one is bigger?
Current sum is bigger.
So will update minus infinity to minus two.
So what I'm writing here is so if basically the current sum just write like this, what is the maximum
sum.
Maximum sum is the maximum of the current maximum sum and the current rate.
So this was minus infinity.
This is minus two and you will update minus infinity to minus two decision maximum now.
And remember, this condition to current sum is minus of two, so we'll again make it zero.
So again, the current sum zero next element is one.
So add one to current sum.
So zero plus one is when No one and minus two, which one is bigger, one is bigger.
So we will make it one.
And this condition so current sum is positive, will move on to the next element minus three.
So what is minus three.
Will add minus three here.
Right.
So one minus three.
The current sum becomes minus two again.
So minus two and one which one is bigger.
One is bigger, do nothing.
And here the current sum becomes less than zero minus two.
So we'll again make it zero.
So we will again make the current term to be zero.
Fine.
Now the next element is four.
So before considering this next element, let's say you have only this Sabeti.
You have only this at a rate.
You have an array which is containing minus one and minus three.
And what is your maximum some?
This algorithm is saying maximum is one and one is the right answer.
Right?
If we consider only this area, then one is the maximum.
So basically this is the proof that this algorithm is working now.
The next element is four.
So zero plus four will be four.
So current sum is four now compared for anyone, four is bigger.
So will update make some some two four and current some is positive.
So do nothing now in this case.
Also if we consider this area, then what is the maximum sum for what is the maximum sum rate.
So again, this is the proof that our algorithm is working now.
The next element is minus one.
So four minus one will be three, be three and four, which is bigger.
Four is bigger.
So do nothing.
Current sum is positive, so do nothing.
Now the next element is two.
So three plus two it will become five.
So five and four, which one is maximum.
Five is maximum.
So updated to five and current sum is positive.
So do not think next element is one.
So five plus one it will become six six and five six is maximum.
So update it to six and current seven is positive, so do nothing.
So next element is minus five, so six minus five it will become one.
One in six.
Six is greater than one.
So do not think algorithm is positive, so do nothing.
Next element is four.
So one plus four it will become five, five and six which was this maximum.
Six is maximum.
So do nothing and is positive.
So do nothing and we will reach the end of the array and the maximum you have is six and six is the
right answer.
So that's how it works, right.
In this case, also, let's do it quickly.
So what is maximum sum?
It is minus infinity.
What is current?
Some obviously it will be zero initially and we need to remember this condition.
So let's start and let's do it quickly, so five zero plus five, it will become five five and infinity
five and minus infinity, so five is greater and continues positive guidance is positive to nothing.
Next element is four five plus four nine nine is lower than five.
Subnet and Grantham's positive do nothing next element minus one nine minus on it.
So nine is good than it.
Do nothing continuous positive.
Do nothing.
Seven, eight plus seven.
It will become fifteen.
Fifteen.
These are the nine updated to fifteen and it is positive do nothing it so fifteen plus eight.
Twenty three.
Twenty three is greater than fifteen.
So update twenty three is positive.
Do nothing you will reach the end.
The maximum is on the tree and that is your right answer.
Right.
So in this case what we are doing, we are iterating over the area only once.
So time complexity is big often and we are creating a few variable current and make some, some space
complexity will be big often.
So this is your time complexity, this is your space complexity and that is our guidance algorithm and
that is our guidance algorithm.
So in next video, we will be writing the code for guidance algorithm.
But this code is going to be very, very simple.
So I highly recommend that you must implement this code yourself.
Right.
And if you face any difficulty, then watch the solution in the next one.
So I will see you in the next video.
Thank you.