1 00:00:06,490 --> 00:00:11,740 In this lecture, we are going to begin discussing the maximum sub array. 2 00:00:12,010 --> 00:00:20,860 So the maximum sub array is going to be finding the sub array 3 00:00:25,360 --> 00:00:26,950 that is at least one value 4 00:00:33,160 --> 00:00:34,930 which has the largest sum. 5 00:00:40,330 --> 00:00:45,160 So and the one rule to this is a sub array 6 00:00:48,490 --> 00:00:52,450 is a contiguous 7 00:00:54,820 --> 00:00:55,930 part of an array. 8 00:00:56,710 --> 00:01:00,490 And if you don't know what that means, I will explain it in just a second. 9 00:01:00,640 --> 00:01:13,870 So let's imagine we have an array with negative two one, negative three four, negative one, two, 10 00:01:13,870 --> 00:01:19,570 one, negative five and four again. 11 00:01:19,570 --> 00:01:22,360 So this is our array. 12 00:01:26,440 --> 00:01:28,530 Let's split up our values. 13 00:01:28,570 --> 00:01:33,360 So a sub array is a contiguous part of an array. 14 00:01:33,370 --> 00:01:36,850 So that means that the values are in order, right? 15 00:01:36,850 --> 00:01:41,950 So -2 to -3, that's not a sub array because you skipped over the one. 16 00:01:41,950 --> 00:01:57,790 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 17 00:01:57,790 --> 00:01:58,420 the end. 18 00:01:58,990 --> 00:02:07,960 So what we want to do is find a sub array in this array, which is at least one value with the largest 19 00:02:07,960 --> 00:02:08,710 sum. 20 00:02:09,190 --> 00:02:16,120 So there's a couple of different approaches that we can look at, but let's try to do one of the most 21 00:02:16,120 --> 00:02:19,060 efficient and let's go with the linear solution. 22 00:02:19,060 --> 00:02:23,290 So we're going to look for the linear solution. 23 00:02:25,330 --> 00:02:29,500 And what we'll do is we're going to start at negative two. 24 00:02:29,920 --> 00:02:32,830 And so obviously we have negative two here. 25 00:02:33,310 --> 00:02:34,540 So we have negative two. 26 00:02:34,540 --> 00:02:44,620 And then if we go to one, so if we added one, we're still at negative one, but one is obviously greater 27 00:02:44,620 --> 00:02:46,990 than negative two. 28 00:02:46,990 --> 00:02:50,470 So there's no point in even worrying about that negative two. 29 00:02:50,470 --> 00:02:57,190 So we'll just go ahead and discard this value because we know that it doesn't make sense to start there 30 00:02:57,190 --> 00:03:02,980 if one is already greater than that. 31 00:03:02,980 --> 00:03:08,520 Two So we'll move our index over to here and now we're starting at one. 32 00:03:08,740 --> 00:03:14,460 Okay, Well now we have a negative three, so we'll add plus negative three, which means we are at 33 00:03:14,470 --> 00:03:17,700 negative two and now we're at negative four. 34 00:03:17,710 --> 00:03:20,620 So now we have plus four. 35 00:03:20,740 --> 00:03:25,630 Well, four again is greater than negative two. 36 00:03:25,630 --> 00:03:32,290 So it doesn't make sense to start out at this one and then add in this negative three. 37 00:03:32,290 --> 00:03:35,050 So we have another negative prefix. 38 00:03:35,320 --> 00:03:42,550 So we'll just go ahead and discard all of these values because it doesn't make sense to include them 39 00:03:42,550 --> 00:03:44,470 when we can start out at four 40 00:03:47,110 --> 00:03:48,010 right here. 41 00:03:48,460 --> 00:03:54,220 So we start out of four now and we add one, so we say plus negative one. 42 00:03:54,220 --> 00:03:55,780 So now we're at three. 43 00:03:56,350 --> 00:03:59,410 So we bring down this two. 44 00:03:59,440 --> 00:04:03,190 So now we add two and now we're at five. 45 00:04:03,310 --> 00:04:08,290 Bring down the one, now we're at six. 46 00:04:09,250 --> 00:04:17,890 And if we bring down this negative five now we're at one plus four is equal to five. 47 00:04:17,890 --> 00:04:25,030 So even if we did this entire sub array, we see that our greatest value here is six. 48 00:04:25,300 --> 00:04:33,610 So for this array, our longest contiguous sub array are excuse me, are just our longest sub array. 49 00:04:33,970 --> 00:04:46,960 So our maximum sub array would be four negative one, two and one, and this would give us six. 50 00:04:47,350 --> 00:04:51,160 So we don't have to worry about any of these other values here. 51 00:04:51,220 --> 00:04:54,040 So in this case we are done. 52 00:04:55,060 --> 00:04:59,740 So if we look at this, there was a common kind of theme that we were looking for. 53 00:04:59,740 --> 00:05:02,500 So we were removing. 54 00:05:05,290 --> 00:05:08,950 It have prefixes. 55 00:05:09,940 --> 00:05:10,330 Right. 56 00:05:10,330 --> 00:05:12,100 So what does that mean? 57 00:05:12,130 --> 00:05:18,820 It means that it doesn't make sense for us if we have a one value here to start out with a negative 58 00:05:18,850 --> 00:05:19,060 two. 59 00:05:19,090 --> 00:05:19,900 So get rid of it. 60 00:05:19,900 --> 00:05:24,310 Or in this case where we had our four well, we had a negative two here. 61 00:05:24,310 --> 00:05:28,060 So that negative two was a prefix to the four. 62 00:05:28,060 --> 00:05:34,420 So it doesn't make sense for us to start out with this negative two that we got from these two values. 63 00:05:34,870 --> 00:05:42,190 So we just kind of slide our index down until we find that value that doesn't have a negative prefix. 64 00:05:42,190 --> 00:05:51,010 And then we begin kind of enumerating all the different sub arrays that can form from this value or 65 00:05:51,010 --> 00:05:59,950 this starting index, which we were able to conclude was this six here, which in turn this ended up 66 00:05:59,950 --> 00:06:02,830 being our maximum sub array. 67 00:06:03,700 --> 00:06:13,660 So what I want you to do is I want you to take some time to try to implement in your solution to this 68 00:06:13,660 --> 00:06:19,000 maximum sub array problem using a dynamic programming approach. 69 00:06:19,000 --> 00:06:27,430 So don't use recursive solution and if you have any questions or you get stuck, please feel free to 70 00:06:27,430 --> 00:06:34,960 ask them in the Q&A section and in the next lecture we will go over my solution to this problem.