Video 2-6: Algorithm Design Teaser - The Maximum Subarray Problem

0:02 Uh this problem is is a well-known algorithmic problem. It's kind of a toy problem I have to tell you. Uh it does have some real applications though like the one I've shown but also some more serious ones and you will revisit it in the tutorials. The maximum subarray problem. Um formally let's define it like this. And here's maybe the first time where uh some of the notation pops up that I'm I'm going to use all over. We're given an array of numbers and I'm always going to write this open close this I mentioned right um the zero is included the n is excluded so I have precisely n numbers um and you could also write it like this and let's say each of these elements is a uh an integer to be a bit more concise In talking about the algorithms, we'll abbreviate these these subsums of a range from I to J. And I really wish um we would write them like this rather is a bit uh maybe then another pair of parentheses around. It's really a range in the same way that I is included but J is excluded, right?

1:22 uh it just makes much of the notation more convenient to do it that way. Um the goal is to compute the value s that corresponds to this maximum subarray value. And here I allow all choices uh of starting indices and ending indices. And I equals J is allowed which you've seen in one of the levels. That means the empty range is also an option. So this this can never be less than zero because you can always pick nothing and that gives you at least zero in case there are negative numbers. Okay. Now uh formally the problem says find me just the sum that is the maximum subarray sum. We'll see that all algorithms that do this can easily also give you the range itself when to buy and when to sell. But uh with the description of the algorithms, we'll we'll focus on just computing s the little s. Okay. Um you've seen that one.

2:34 Apart from this obviously um very clever application which may only make sense as a hindsight analysis. It's one of the uh things that people do when they want to convince you that time in the market beats timing the market. If you uh long-term invest then you rather want to invest uh whenever you have the money available instead of waiting for the right moment to buy. Oftentimes if you plot this over historic uh times then you would have won more by just leaving leaving your money invested for longer than waiting for the right point in time. And in a way this subarray problem is the hypothetical post hawk optimum if you know what happens. uh there's a bit a few more serious applications that we'll come back to in particular if you go to two-dimensional ranges of numbers but for here just one one d uh one array of numbers okay a few things to fix um we'll say the input size of the problem is the number of numbers that we have we don't care how big the numbers are here so we'll assume that these are integers and are not humongous But it turns out this doesn't make a huge difference. And for the cost of an algorithm, we count the number of additions it does. That's what you have to do to determine these sig. So that sounds like a reasonable metric.

4:03 Okay. Um, in the interest of time, let me skip that question. Maybe you can think about what you would expect if I gave you a a longer and longer such array of numbers. How fast should we be able to do this? Um, if you want, I'm gonna open the question and you can send in your your guesses or your your thoughts.

4:27 Um, I rather want to move on for now. I'll also use this as the first example where we design an algorithm. Uh, I've if you've been in algorithms data structures, you know this already. Uh whenever you design an algorithm, you should document the following four steps that includes exercise problems and exams. Uh you first want to and this is for the write up. This is not necessarily the order in which you come up with things. But your write up of a an algorithm design should start with an idea uh that roughly describes the approach you followed. And we'll spend much of the term in going through different design techniques that can go as uh the idea into this slot. Uh for now just think about it as a two three sentence summary of of your idea. And I guess the idea is here that if you give this to an algorithms expert that should be all they need to know about your solution to complete the rest. Of course if you're not yet there it's a bit hard to say sometimes how much that is. Second part, you want to give some concrete code that describes what the algorithm does. This is often a bit more lengthy. So, it's important to preface it with an idea so that it's easier to read. Uh, ideally, you write this as a sort of structured. It doesn't need to be a formal program. I'll show you some examples that are a bit on the formal side. It can also be just a bullet list or an enumeration with with items.

6:02 The idea is that it's unambiguous enough that you could go from there to real code without too much hassle. And then there's two things that um in algorithms and data structures we also did, but here really is a bit more of the focus. We want to prove that the algorithm does what it claims to do that it solves the correct the problem correctly. Um and we want to analyze how much resource time and space the algorithm needs. question.

6:38 Yeah, exactly. So, these can be one of the known paradigms, divide and conquer or greedy, etc. Maybe with a bit more detail. The point is um I'm not assuming that you know these already. They will come up as as topics in this module. So in hindsight maybe this is often times something you read but for now uh if you don't know what I'm talking about here relax you'll as in a couple of weeks will okay so that's the four steps we also always want to do these four and I'm going to showcase them on this toy example a bit before you do anything with algorithms first work out what is the most primitive approach and how far does that give you usually call this the brute force approach because it just beats the problem to death with throwing enough resources at it. It's not always a stupid idea. Sometimes it's good enough. Simplest thinkable solution. Well, just try all possible answers, compute how good they are, and pick the best.

7:40 Remember the best, right? Uh so as code, that's not too hard to do. I have my S which is my current best. I can start at zero because it's always okay to pick the empty range. Then I go through all starting indices I and all ending indices that's buy and sell. Uh here J starts at I but other than that this is rather u boring. And then I need to compute the sum from I to J. So I do that in a variable T that starts at zero. And then for all values in the range again here excluding J that's the way we decided defined this S of J. So all of this computes S of I comma J in T. So after this loop here T contains the S of J. If that is bigger than what I've previously found I remember it otherwise I just continue. Clearly that's that gets the job done.

8:45 Okay. Uh I think um nobody even tried this on the game because it's horrendously wasteful. But uh the good thing is the correctness proof is very easy. It does precisely what the definition says we're supposed to do. So it can't really go wrong. Now for the algorithm analysis, let's do this as if we cared about every single addition. It's easy enough to do here.

9:22 First of all, I can rewrite a for loop just as a sum. For every value in I, I'm doing whatever this loop does. For every value in J inside that, I'm doing whatever this costs. And then for every K, I'm doing whatever this costs. Now, the only addition I ever do is here. That's my one. I pay one addition for each of these innermost iterations. And so all I need to do is plug in the right boundaries. I goes from 0 to N minus one. That's just copied. J goes from I to N. And K goes from I to J minus one. That's all I need to do to pick out the number of additions. The rest is algebra. And let's maybe do it here. So um this innermost sum is easy. It just sums up one. So if I just pick out this sum, that's going to be what? As many entries as I have sumat. So it's j -1 - i + 1.

10:21 Upper bound minus lower bound + one because I'm including both. Of course, that's nothing but j minus i. Okay, that's the first step been written nicely. Now um we have a sum that sums over i and j. Now here um I think we want to sum in reverse. So if you look at this sum, it goes the this internal term the smallest j I put in is i. So this goes from zero up to when I put in j to n, it's n minus i. and I sum up all the values in between. I might as well say I'm summing up all the numbers between zero and n minus i and put just j in the sum. That's what I've done here. I've only rewritten this. J goes from zero to n minus i. Now, exactly the ranges of this inner sumant and I'm summing over j. Why do I do that? Well, first of all, you may of course know that this sum has a certain value. It's little Gaus sum.

11:36 So if you sum up the first two integers, the first few integers like this, you know how to do this, right? So you copy the same in reverse.

11:56 Then you notice if you sum this all up, you always get seven. How many sevens do you get? Well, as many as you had thinks. So, this needs to be 7 x 6. But I've done it twice now. So, you have to divide by two.

12:14 The general case if you sum i from one up to n over i is you have n + one as the sum of these uh columns and you have n rows but then you've summed everything twice. In case you can't remember these things, you're in good company.

12:41 And at this point, let me go to my um copy of the TCS cheat sheet, the theoretical computer science cheat sheet, which is not at all by myself. Um but I've smuggled in our definitions of big O. The rest is unchanged from an old latte showcase.

13:03 And among other things, it has a collection of formulas. For example, these sums. And you see the first one is what I've just uh written on the slide.

13:22 We will give you a copy of this cheat sheet or the the relevant pages of it in the exam. So you can you don't need to learn these by heart if you feel they're a bit hard to memorize. Uh that shouldn't be the point. This is again it's pure algebra. You'll uh practice this a bit in the tutorials, but I'm I'm fine if you uh look these up in the exam. So if I plug this in here, oh, we start at zero. Well, of course, I'm summing zero and that does nothing. And then n minus i. Well, that's just plugging it in here. So you get this lovely term, the upper bound, the upper bound plus one divided by two. Now we have another sum around this. And this looks rather scary and messy. The first thing to notice it's again the scary part is that we sum n minus i and reverse that. If I look what happens with my values of i. I start with i at zero. Then this is n and n + 1 / two. That's the one extreme end. If I insert the smallest value for i, if I insert the largest value for i, I get n minus n minus one. So that's one. And the same thing + 1. So it's 1 * 2 over two.

14:46 And I have all the numbers in between here for I mean for the different values of i. I don't have all values here of course but I can rewrite that sum as I and I + 1. The two goes out as a constant factor and then from i and i + 1 here again the smallest value I get here is 1 and 1 + 1 and the largest is n. So really this goes from 1 to n / i * i + 1. And then uh this I can split that's i^2 + i. So I can split the sum into two. And now this second thing is of the form that we already know how to solve. Same sum again. And this one eh even more scary. But uh luckily it's also one on the cheat sheet. So this is the one that I never um can remember by heart. So I can remember the first but then it stops.

16:01 So let's keep that here as a reminder. And all you need to do is plug in the values for n. Uh I've prepared that. That's just the formula. Um this one right you see it's the same term I just put the 1/2 in front of the sum already in the fraction this one so it's the the 12 same here now this um happens to be um you can further simplify this to put it on one fraction That's just bringing it on the same denominator and uh working out that you can factoriize the denom the numerator and then you may or may not recognize this as uh some some specific closed form even but okay let's um at this point say this formula is is precise but a bit annoying to interpret. What we care about is the tilda asmtoic and for that I multiply it out I get a an n cubed up here and the 1 / 6 stays okay so after a really long story we found we have a cubic algorithm for this problem and that's really bad.

17:28 This is totally useless. Uh it gets the job done but is so slow it wouldn't even work for rather small examples. So where does this algorithm not um where does this algorithm waste effort? >> Yeah.

17:59 >> And then combining solutions. >> Okay, this is um this is a very good idea. we could somehow try to combine things we've already calculated which also means we need to remember them. Um, of course the way the way you said it is rather generic so you can do this smarter and less smart. Let me only because we're out of time show you the less smart version. The thing where this algorithm is really so stupid that if you do it by hand on an example, it screams in your face that this is the wrong way to do it is that it re-evaluates this sum over and over again. Each time for each value I and J, I start from scratch to sum up the numbers. I don't need to. Right? If I um include if I make J one bigger, I'm just adding another number at the end. Let's just add that number into the sum, please.

18:49 Right? So um clearly you can get this sum here by just adding one more number. If you do that the triple loop is gone and you still loop over all I and J. But here you use that you're iterating over the J's in a convenient order so that you can just add in the last element in a single addition. The correctness proof stays the same. I'm just still trying all options, but uh I at least avoid summing them up over and over again. The analysis is also the same kind of uh mechanic. You put the the two sums with the single addition here and it turns out you get to quadratic. Maybe not surprising because it's two nested loops. Also, if you take out all starting and end positions that end that is end choose two. It has to work out to this, but it's at least way better than the cubic algorithm.