Name: Kadane's Algorithm to Maximum Sum Subarray Problem
Uploaded: 2020-03-28T10:55:40.000Z
Duration: 11 min 17 s
Description: Thousands of YouTube videos with English-Chinese subtitles! Now you can learn to understand native speakers, expand your vocabulary, and improve your pronunciation...

Basic passive voice

in this video, I'm going to discuss the optimal solution to the maximum sub array problem, which is called contains our rhythm.

Now let me explain what the maximum summary problem is.

Modal verbs - B1

Sub arrays, basically an array within the rate.

So an example of a separate would be to one in this example, or just wanted women negative three.

But if we had number three, let's say on one that's not a separate because a submarine needs to be contiguous elements.

So a subway is a set of continuous elements within the given array, and the problem here is finding the sub array with the maximum some.

If you look at this sub array to one, the sum is two plus one.

If we look at this sub array with negative three, the Psalmist, obviously just in another three, and we're trying to find the one with the maximum some in this example.

It's actually 21 with the sound three on.

The simplest solution to this problem is the brute force solution, basically checking all the possible sober res on picking the one with the maximum some.

So I would check the sub array starting at the first index and then check the ones starting at the second index.

And so it's a good solution, but he would take on older, off and square time on.

The optimal solution to this problem is what's called today's Argo them.

And when I explained the idea behind it first and then we're gonna go into the actual algorithm, the idea is very simple.

We're gonna look at each index, and we're gonna ask ourselves, What's the maximum subway ending at this index?

So for the first thing next, the maximum subway ending at DIS Index is obviously just one on for the sick and the next.

The maximum subway ending at this index could be either one negative three or just in the 33 on the maximum.

One of those is one negative three for the 30.

The maximum subway or the sub array, with the maximum some ending at this index could be either too negative.

32 or 1232 And the maximum one of those is, too.

If you compare the sums and we're gonna do the same thing for each E next for the rest of the Mrs on at the end, we're gonna compare those sub arrays on.

We're gonna find the maximum one of those in this case, that's to one with the some three.

As you can see, the idea is very simple, but it's not very efficient, actually.

At least it's gonna take in order of and square time.

But the interesting idea from Canadians argo them is that we can do much better than that.

Actually, we can run a under a leaner time, so let's see how we can do it.

Let's say we're using the same strategy here.

We're looking at each in next, and we're trying to find the maximum sub array ending at that index on.

Let's say we're looking at the 30 next and we know what the sub array from the previous the nexus, and we're trying to find the maximum silvery for this index or the maximum sobre ending at this index.

So the interesting idea from cadenza algorithm is that that's that maximum separate.

The local Maxim's ovary is either this element, the current element or the current element combined with the previous maximum subway.

In this case, that's one the other three.

We can just compare these and ignore all the other several raise on.

That's gonna be the local maximum sobering ending at this index.

So we're gonna do the same thing for all of the anus is, except for the 1st 1 because the 1st 1 we just picked the first Ellemann as a maximum subway.

And once we did that, we're gonna pick the maximum one of those.

And that's gonna be the global maximum sub array on this algorithm is much faster than the brute force algorithm.

Now, you might ask, Does he actually work?

So let me explain that Let's just say we're giving this array on.

We're running today's OG with ammonia and now we add the anti next.

Now, let's just say the element here is X on dhe.

We know what the summary ending at the previous in Texas.

Let's call the M on the core Idea from cadets are good.

Um, was that the maximum sub array ending at the empty?

Next is either just the current element X or the current Ellman X combined with em.

So M X And as you can see em, could be any number of elements.

Let me prove to you this is in fact, the case to do that.

Let's just assume that this is actually not the case that the maximum sub array ending at this omen is neither ex nor M X is actually t X or something on.

So the tea is either longer than them boy has more elements than M Oh, it has less elements.

But T is not empty because if he was empty, it would be the same as just X.

And what I'm gonna show now is that the sum off T X is on.

Some with this symbol is less than the sum off M X.

This is actually less than or equal to, but this is gonna show that the T X is not the maximum sub array ending at the current in next.

Anything next, or at least it's not the unique maximum summary on it's very simple to show.

So the sum of T X is the sum of tea plus X on.

The sum of MX is obviously the sum of em plus X, because we know that M is the maximum some ending at the previously next it's at least larger than or equal to the some.

Off T, which is also a sub array that ends at the previous index on this result, shows that if you look at these equations, the sum of T X is less than a week or two.

The some off MX, which in turns shows that the maximum subway ending at the current index or the lengthy next needs to be either X, the current Eman or the current German ex combined with M, which is the maximum sub array ending at the previously next.

If we were trying to find multiple maximum subways, the algorithm would be slightly different.

But the idea is the same now that we've explored how the algorithm works, let's just dive into the code here.

I'm just defining my function on the input is gonna be the given array on the example I'm gonna use here.

Is this one on the output is gonna be the some off the maximum separate.

And I'm not gonna worry about where the maximum summary is for now.

First of all, I'm gonna usual eyes all my valuables to the first element in the array and the max current.

Is this some off the current maximum separate or the maximum sub array that ends at the current?

You Next on Max Global keeps track off the global maximum some.

And since the first element of the array is negative too, I mean, you socializing both of them to get him to and I'm gonna eat a right the index I from one two the lengths mind this one.

So that's gonna be in this example from 1 to 3, the last index.

Now let's look at the second index or the next one.

What we're asking ourselves is, what's the maximum sub array?

Ending at this index is either three or negative 23 on the larger one is or the one with the largest sum is three So that's the maximum subway ending at this index on the some of that sub array is three.

In the code that's expressed as Max current is the maximum off or the larger off a I on dhe Max Kern plus a I.

And if the Max current is larger than Max Global than update the Max Global.

So let's do the same thing with the other illnesses.

Let's look at the 30 next to which is this one?

Well, we're gonna ask ourselves Here is what a game.

What's the maximum subway ending at this index is either too or to combined with the previous maximum subway 32 And obviously this is the one with the largest sum.

We're gonna update the current some ongoing update, their current global some as well.

We're just gonna do the same thing for the last index on for the last index, the current some is gonna be four.

We're not gonna update the global son because that's larger than the current some.