1 00:00:06,660 --> 00:00:14,310 In this lecture, we are going to go over my solution to the maximum sub array assignment assigned in 2 00:00:14,310 --> 00:00:15,540 the previous lecture. 3 00:00:15,540 --> 00:00:23,520 I hope you had a successful attempt at creating a solution for the assignment. 4 00:00:23,520 --> 00:00:29,640 And if you have any questions about my solution, please feel free to ask them in the Q&A section. 5 00:00:30,480 --> 00:00:35,670 So I went ahead and kind of set up the function that we're going to use. 6 00:00:35,970 --> 00:00:42,960 Obviously, we need to pass in an array here, so I'm going to do mine of Type I 32. 7 00:00:42,960 --> 00:00:52,860 And then in order for us to return the maximum subquery value, we want to return an I 32. 8 00:00:53,220 --> 00:00:59,130 So I'm going to use a temporary array to kind of store some values. 9 00:01:00,450 --> 00:01:14,310 That way I have a little bit of room to work with and we want to just go ahead and assign in a value 10 00:01:14,310 --> 00:01:16,500 into that temporary array. 11 00:01:17,850 --> 00:01:25,020 That way we have at least one result and we want to create our result array where our answer are our 12 00:01:25,020 --> 00:01:33,600 result variable, which is going to be the answer that we return at the end of the function. 13 00:01:34,590 --> 00:01:44,190 So since we already started out at index zero, we can say for one or excuse me for I and one to the 14 00:01:44,190 --> 00:01:45,390 length of the array. 15 00:01:47,400 --> 00:01:54,600 And then if temp of I minus one is greater than zero. 16 00:01:54,600 --> 00:02:06,720 So we do not have a negative prefix prefix here, then we want to say temp of I is equal to DPI excuse 17 00:02:06,720 --> 00:02:21,390 me temp temp of I minus one and plus the next value in the array that we have passed in. 18 00:02:23,880 --> 00:02:37,170 Otherwise temp of I is equal to array of I, in which case we are going to just go ahead and move our 19 00:02:38,730 --> 00:02:51,150 index up one and then for our result we want it to be equal to the max value of our temp of. 20 00:02:51,150 --> 00:02:59,580 I so remember from the longest common common sub sequence max is going to compare result to temp of 21 00:02:59,580 --> 00:03:07,830 I and whoever wins that comparison, whoever is greater is now going to be assigned to the result variable. 22 00:03:07,920 --> 00:03:12,510 And lastly, we want to return our result. 23 00:03:13,500 --> 00:03:17,040 So this is all we actually have to do for the maximum sub array. 24 00:03:17,190 --> 00:03:21,570 So let's create some test cases to make sure that it all works. 25 00:03:22,230 --> 00:03:24,180 So we will test it out. 26 00:03:24,180 --> 00:03:33,360 So let's create a test F in test max sub array. 27 00:03:36,660 --> 00:03:47,400 So we say let array is equal to a vector and we will say one zero, five and eight. 28 00:03:47,430 --> 00:03:49,530 We'll go non negative to start. 29 00:03:49,950 --> 00:04:06,750 And in this case if we call max sub array and pass in our array, we expect what is one plus zero plus 30 00:04:06,750 --> 00:04:07,680 five plus eight. 31 00:04:08,100 --> 00:04:12,150 So 14, that is what we would expect to be here. 32 00:04:12,150 --> 00:04:17,700 So we have one plus zero plus five plus eight. 33 00:04:17,700 --> 00:04:20,040 So that's a very simple test case. 34 00:04:20,880 --> 00:04:23,010 Let's do another one. 35 00:04:23,280 --> 00:04:33,120 Let's say let array two equals vector and we'll do some negative values in this one, negative three, 36 00:04:33,780 --> 00:04:39,540 negative one, negative eight and negative two. 37 00:04:40,080 --> 00:04:51,720 And here we expect to see only negative one returned because nothing greater than negative one can be 38 00:04:51,720 --> 00:04:52,800 added on to this. 39 00:04:52,800 --> 00:05:04,650 So we would expect assert equals of our max sub array of our array two to be negative one. 40 00:05:07,320 --> 00:05:16,950 Do another ray and we'll make this one have a couple of different mixed matches between negatives and 41 00:05:16,950 --> 00:05:18,060 non negatives. 42 00:05:18,240 --> 00:05:29,460 So we will say let's go negative four, three, negative two, 43 00:05:32,010 --> 00:05:37,500 five and minus three. 44 00:05:39,780 --> 00:05:54,300 So in this case we would expect it to be negative three plus a negative two plus a five, which equals 45 00:05:55,380 --> 00:05:57,690 six and we don't have negative three. 46 00:05:57,690 --> 00:05:58,800 It's regular three. 47 00:05:59,220 --> 00:06:00,030 Yes. 48 00:06:00,090 --> 00:06:00,780 All right. 49 00:06:01,140 --> 00:06:11,010 So we'll do our assert equals here max sub array on a reference to array three and we would anticipate 50 00:06:11,010 --> 00:06:12,330 six being returned. 51 00:06:12,330 --> 00:06:14,700 So these are three pretty good test cases. 52 00:06:14,700 --> 00:06:21,420 So if we run them, we see that they pass successfully, all three of them do. 53 00:06:22,740 --> 00:06:28,650 So it looks like my implementation of the MAX summary is working correctly. 54 00:06:28,800 --> 00:06:36,090 So again, I hope you enjoyed this assignment and I hope you enjoyed learning about the concept of dynamic 55 00:06:36,090 --> 00:06:37,110 programming. 56 00:06:38,070 --> 00:06:45,270 If you have any questions regarding dynamic programming or my solution to the Max sub array, please 57 00:06:45,270 --> 00:06:52,770 feel free to ask them in the Q&A section and I will see you in the next section when we start discussing 58 00:06:52,770 --> 00:06:55,110 the graph data structure.