In this lecture, we are going to begin discussing the maximum sub array.
So the maximum sub array is going to be finding the sub array
that is at least one value
which has the largest sum.
So and the one rule to this is a sub array
is a contiguous
part of an array.
And if you don't know what that means, I will explain it in just a second.
So let's imagine we have an array with negative two one, negative three four, negative one, two,
one, negative five and four again.
So this is our array.
Let's split up our values.
So a sub array is a contiguous part of an array.
So that means that the values are in order, right?
So -2 to -3, that's not a sub array because you skipped over the one.
So 2 to 1 would be one, 2 to 3, 2 to 4, 2 to -1, and so on and so forth all the way over here to
the end.
So what we want to do is find a sub array in this array, which is at least one value with the largest
sum.
So there's a couple of different approaches that we can look at, but let's try to do one of the most
efficient and let's go with the linear solution.
So we're going to look for the linear solution.
And what we'll do is we're going to start at negative two.
And so obviously we have negative two here.
So we have negative two.
And then if we go to one, so if we added one, we're still at negative one, but one is obviously greater
than negative two.
So there's no point in even worrying about that negative two.
So we'll just go ahead and discard this value because we know that it doesn't make sense to start there
if one is already greater than that.
Two So we'll move our index over to here and now we're starting at one.
Okay, Well now we have a negative three, so we'll add plus negative three, which means we are at
negative two and now we're at negative four.
So now we have plus four.
Well, four again is greater than negative two.
So it doesn't make sense to start out at this one and then add in this negative three.
So we have another negative prefix.
So we'll just go ahead and discard all of these values because it doesn't make sense to include them
when we can start out at four
right here.
So we start out of four now and we add one, so we say plus negative one.
So now we're at three.
So we bring down this two.
So now we add two and now we're at five.
Bring down the one, now we're at six.
And if we bring down this negative five now we're at one plus four is equal to five.
So even if we did this entire sub array, we see that our greatest value here is six.
So for this array, our longest contiguous sub array are excuse me, are just our longest sub array.
So our maximum sub array would be four negative one, two and one, and this would give us six.
So we don't have to worry about any of these other values here.
So in this case we are done.
So if we look at this, there was a common kind of theme that we were looking for.
So we were removing.
It have prefixes.
Right.
So what does that mean?
It means that it doesn't make sense for us if we have a one value here to start out with a negative
two.
So get rid of it.
Or in this case where we had our four well, we had a negative two here.
So that negative two was a prefix to the four.
So it doesn't make sense for us to start out with this negative two that we got from these two values.
So we just kind of slide our index down until we find that value that doesn't have a negative prefix.
And then we begin kind of enumerating all the different sub arrays that can form from this value or
this starting index, which we were able to conclude was this six here, which in turn this ended up
being our maximum sub array.
So what I want you to do is I want you to take some time to try to implement in your solution to this
maximum sub array problem using a dynamic programming approach.
So don't use recursive solution and if you have any questions or you get stuck, please feel free to
ask them in the Q&A section and in the next lecture we will go over my solution to this problem.