in this video I'm going to discuss the
optimal solution to the maximum
sub-array problem which is called
cadenza algorithm now let me explain
what the maximum several very problem is
you might ask what's a sub array a sub
array is basically an array within an
array so an example of a sub array would
be 2 1 in this example or just one
element negative 3 or it could be the
whole array that's also a sub array but
if we had negative 3 let's say and 1
that's not a sub array because a sub
array needs to be contiguous elements so
a sub array is a set of contiguous
elements within the given array and the
problem here is finding the sub array
with the maximum sum here's what I mean
if you look at this sub array 2 1
the sum is 2 plus 1 equals 3 and if we
look at this sub array with negative 3
this arm is obviously just negative 3
and we are trying to find the one with
the maximum sum in this example it's
actually 2 1 with the sound 3 and you
can check it yourself to the simplest
solution to this problem is the brute
force solution basically checking all
the possible sub arrays and picking the
one with the maximum sum so I would
check the sub array starting at the
first index and then check the ones
starting at the second index and so on
it's a good solution but it would take
an order of N squared time and it's not
the optimal solution the optimal
solution to this problem is what's
called contains our Gotham I'm going to
explain the idea behind it first and
then we're going to go into the actual
algorithm the idea is very simple we're
going to look at each index and we're
going to ask ourselves what's the
maximum sub-array ending at this index
so for the first index the maximum
subway ending at this index is obviously
just 1 and for the second index the
maximum sub-array ending at this index
could be either 1 negative 3 or just
negative 3 and the maximum one of the
close is one negative three I'm for the
30 next we're going to do the same thing
the maximum sub-array or the sub-array
with the maximum sum ending at this
index could be either 2 negative 3 2 or
1 negative 3 2 and the maximum one of
those is 2 if you compare the sums and
we're going to do the same thing for
each index for the rest of the indices
and at the end we're going to compare
those sub arrays and we're going to find
the maximum one of those in this case
that's two one with the sum 3 as you can
see the idea is very simple but it's not
very efficient actually at least it's
going to take an order of N squared time
but the interesting idea from Canadians
algorithm is that we can do much better
than that actually we can run it under a
linear 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
index and we are trying to find the
maximum sub array ending at that index
and let's say we're looking at the 13 X
and we know what the sub array from the
previous index is and we're trying to
find the maximum so very for this index
or the maximum sub array ending at this
index so the interesting idea from
contains algorithm is that that's that
maximum sub array the local maximum sub
array is either this element the current
element or the current element combined
with the previous maximum sub array in
this case that's 1 negative 3 we can
just compare these and ignore all the
other sub arrays and that's going to be
the local maximum sub array ending at
this index so we're going to do the same
thing for all the indices except for the
first one because the first one we just
pick the first element as the maximum
sub array and once we did that we're
going to pick the maximum one of those
and that's going to be the global
maximum sub array
and this algorithm is much faster than
the brute-force algorithm as I said it
runs in a linear time now you might ask
does it actually work if it does why
does it work so let me explain that
let's just say we're giving this array
and we're looking at the nth index
we're running contains algorithm onion
and now we add the nth index and let's
just say the element here is X and we
know what the sub-array ending at the
previous index is and let's call it m
and the core idea from contains
algorithm was that the maximum sub array
ending at the empty index is either just
the current element X or the current
element X combined with M so M X and as
you can see M could be any number of
elements and 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 element is neither X nor M X
it's actually TX or something and I'm
going to find a contradiction there so
that T is either longer than M or it has
more elements than M oh it has less
elements it doesn't matter either way
but T is not empty because if it was
empty it would be the same as just X and
what I'm going to show now is that the
sum of TX is and let's denote the sum
with this symbol it's less than the sum
of M X this is actually less than or
equal to but this is going to show that
the TX is not the maximum sub array
ending at the current index anything in
X
or at least it's not the unique maximum
sub-array and it's very simple to show
so the sum of TX is the sum of t plus X
and the sum of em X is obviously the sum
of M plus X and because we know that M
is the maximum sum ending at the
previous index it's at least larger than
or equal to the sum of T which is also a
sub array that ends at the previous
index and this result shows that if you
look at these equations the sum of TX is
less than or equal to the sum of em X
which in turn shows that the maximum
sub-array ending at the current index or
the enth index needs to be either X the
current element or the current element X
combined with M which is the maximum
sub-array ending at the previous index
if we were trying to find multiple
maximum sub arrays 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
and the input is going to be the given
array and the example I'm going to use
here is this one and the output is going
to be the sum of the maximum sub array
and I'm not going to worry about where
the maximum sub array is for now first
of all I'm going to initialize all my
variables to the first element in the
array and the max current is the sum of
the current maximum sub array or the
maximum sub array that ends at the
current index and max global keeps track
of the global maximum sum and since the
first element of the array is negative
two I mean
rising both of them to negative two and
I'm going to iterate the index i from 1
to the length minus 1 so that's going to
be in this example from 1 to 3 the last
index now let's look at the second index
the for the index 1 this one what we are
asking ourselves is what's the maximum
sub-array ending at this index it's
either three or negative 2 3 and the
larger one is or the one with the larger
sum is 3 so that's the maximum sub-array
ending at this index and the sum of that
sub array is 3 so we're going to update
C and that's larger than the global sum
so we're going to update that as well
in the code that's expressed as Max
current is the maximum of or the larger
of AI and Max current plus AI and if the
max current is larger than max global
then update the max global so let's do
the same thing with the other indices
let's look at the third index 2 which is
this one what we're going to ask
ourselves here is what again what's the
maximum sub array ending at this index
it's either 2 or 2 combined with the
previous maximum sub array 3 2 and
obviously this is the one with a larger
sum so we're going to pick this one
we're going to update the current sum
and we're going to update the current
global sum as well and we're just going
to do the same thing for the last index
and for the last index the current sum
is going to be 4 and we're not going to
update the global sum because that's
larger than the current sum and at the
end we're going to return this number
the global sum and that corresponds to
the maximum sub array in this example 3
2 all right that's it for the video and
I hope you liked it if you want to watch
more videos like this you can click
right here to subscribe to my channel
and see you soon