In this lecture, we are going to go over my solution to the maximum sub array assignment assigned in
the previous lecture.
I hope you had a successful attempt at creating a solution for the assignment.
And if you have any questions about my solution, please feel free to ask them in the Q&A section.
So I went ahead and kind of set up the function that we're going to use.
Obviously, we need to pass in an array here, so I'm going to do mine of Type I 32.
And then in order for us to return the maximum subquery value, we want to return an I 32.
So I'm going to use a temporary array to kind of store some values.
That way I have a little bit of room to work with and we want to just go ahead and assign in a value
into that temporary array.
That way we have at least one result and we want to create our result array where our answer are our
result variable, which is going to be the answer that we return at the end of the function.
So since we already started out at index zero, we can say for one or excuse me for I and one to the
length of the array.
And then if temp of I minus one is greater than zero.
So we do not have a negative prefix prefix here, then we want to say temp of I is equal to DPI excuse
me temp temp of I minus one and plus the next value in the array that we have passed in.
Otherwise temp of I is equal to array of I, in which case we are going to just go ahead and move our
index up one and then for our result we want it to be equal to the max value of our temp of.
I so remember from the longest common common sub sequence max is going to compare result to temp of
I and whoever wins that comparison, whoever is greater is now going to be assigned to the result variable.
And lastly, we want to return our result.
So this is all we actually have to do for the maximum sub array.
So let's create some test cases to make sure that it all works.
So we will test it out.
So let's create a test F in test max sub array.
So we say let array is equal to a vector and we will say one zero, five and eight.
We'll go non negative to start.
And in this case if we call max sub array and pass in our array, we expect what is one plus zero plus
five plus eight.
So 14, that is what we would expect to be here.
So we have one plus zero plus five plus eight.
So that's a very simple test case.
Let's do another one.
Let's say let array two equals vector and we'll do some negative values in this one, negative three,
negative one, negative eight and negative two.
And here we expect to see only negative one returned because nothing greater than negative one can be
added on to this.
So we would expect assert equals of our max sub array of our array two to be negative one.
Do another ray and we'll make this one have a couple of different mixed matches between negatives and
non negatives.
So we will say let's go negative four, three, negative two,
five and minus three.
So in this case we would expect it to be negative three plus a negative two plus a five, which equals
six and we don't have negative three.
It's regular three.
Yes.
All right.
So we'll do our assert equals here max sub array on a reference to array three and we would anticipate
six being returned.
So these are three pretty good test cases.
So if we run them, we see that they pass successfully, all three of them do.
So it looks like my implementation of the MAX summary is working correctly.
So again, I hope you enjoyed this assignment and I hope you enjoyed learning about the concept of dynamic
programming.
If you have any questions regarding dynamic programming or my solution to the Max sub array, please
feel free to ask them in the Q&A section and I will see you in the next section when we start discussing
the graph data structure.