I will start with the everyday example. Think about the last time you used the index section of a book to find a keyword or the time when you looked through your phone's contact list to find a specific person. In both of the cases the words were alphabetically sorted.
A brute force approach in this case would be to start from the beginning of the index or the contact list and then proceed reading every single word until we find the specific one we were looking for. However, since we know how the list of the words are sorted we actually apply divide and conquer algorithms ourselves!
Think of it this way: instead of searching for the whole words you decide to quickly go through each words based on the first two or three letters. So now, our problem is divided into a sub-problem. The way we solve this problem is to skip pages until the first letter meets, and then skip some more until the second, and then the third ... whichever letter we want to stop at matches. This was a recursive solution. We started from the left letter of the words and recursively solved for each one of them. After we match adequate number of letter we will now have the result of our solutions to divided problems: the combination of the matches, solutions, which is equal to the words we were looking for in the beginning.
If you think of it this way, we inadvertently solve many problems in our everyday life with several different algorithm paradigms! Now we will try to solve a harder problem.
Let's say you have a list called A. Consider all the possible list slices that could be taken from A and find the list slice with the maximum sum of elements. Notice that the sum of an empty list is 0 and sum of a list with one element is that element itself. Also notice that the sum of a list of positive numbers is the largest slice, so the problem only gets interesting when we have negative numbers inside our list.
Now let's revise our steps for divide and conquer:
1- Divide problem into sub-problems
2- Solve sub-problems recursively
3- Combine solutions from 2nd step to get the final answer
We should now think about the recursive idea. It is always easier to deal with a half list than a full list. So let's assume that we divided a list into half, and then found the maximum sum on the left side and then the maximum sum on the right side. If we recursively continue this thought process, we will eventually reach many separate list slices of length = 1. We already know that the maximum sum of a list of length 1 is equal to the only element in the list.
Let's try to trace this recursive idea. Assume that we have a list of size 2. Then the list will be separated into two lists of 1 element. Then our main list's maximum will be equal to the maximum of either of those lists. Now let us assume that we have a list of size 4. Then we will have two lists of size 2. We do not need to trace more since we already did it in the previous case. Our main lists maximum will be the maximum of the either length 2 lists, which will have a maximum of one of the 4 1 element lists.
Even though the recursive idea is correct, we are missing something here. What if the maximum of a list includes few elements from the left side and the right side of the list? This adds a third sum to check for every sub-list. Now we need to think about the best way to deal with this third sum. We already know that there are two maximum sums on either side of the list. Let us call them max left and max right. And let us call the third one max middle. We know for a fact that max middle is not going to include any number that comes before the sub-list that makes up the max left in our original list, and we also know that there won't be any numbers in max middle which come after the max right. Why? Well, we know that any number that comes before the max left or comes after the max right is not beneficial to the number sum, hence they are not included in those sums.
Now we know a little more about the interval we need to be looking for the max middle. It is any numbers between the sub-list that makes max left and the sub-list that makes up the max right. We can go further on and say that max middle has two components: max middle left and max middle right. We can run a simple for loop in each one of our recursive calls to calculate the max middle left and max middle right, and then add them up to find the max middle. Since we are constantly mentioning positions in a list, it would probably be a good idea to carry index information with each recursive call.
Now I will type down the general idea:
We will take a list of size n, and we will divide it into two lists of size n/2. In each recursive call we will divide the lists into half to calculate the max left, right and middle associated with them. Each recursive call will return the maximum of max left, max right and max left, because as we discussed earlier a maximum subsequence of a sub-list will come in handy when we are looking for the maximum subsequence of the main list.
I think I have discussed about my algorithm enough. So I will share my python code to solve the problem. Where A is our input list.
Let's try to trace this recursive idea. Assume that we have a list of size 2. Then the list will be separated into two lists of 1 element. Then our main list's maximum will be equal to the maximum of either of those lists. Now let us assume that we have a list of size 4. Then we will have two lists of size 2. We do not need to trace more since we already did it in the previous case. Our main lists maximum will be the maximum of the either length 2 lists, which will have a maximum of one of the 4 1 element lists.
Even though the recursive idea is correct, we are missing something here. What if the maximum of a list includes few elements from the left side and the right side of the list? This adds a third sum to check for every sub-list. Now we need to think about the best way to deal with this third sum. We already know that there are two maximum sums on either side of the list. Let us call them max left and max right. And let us call the third one max middle. We know for a fact that max middle is not going to include any number that comes before the sub-list that makes up the max left in our original list, and we also know that there won't be any numbers in max middle which come after the max right. Why? Well, we know that any number that comes before the max left or comes after the max right is not beneficial to the number sum, hence they are not included in those sums.
Now we know a little more about the interval we need to be looking for the max middle. It is any numbers between the sub-list that makes max left and the sub-list that makes up the max right. We can go further on and say that max middle has two components: max middle left and max middle right. We can run a simple for loop in each one of our recursive calls to calculate the max middle left and max middle right, and then add them up to find the max middle. Since we are constantly mentioning positions in a list, it would probably be a good idea to carry index information with each recursive call.
Now I will type down the general idea:
We will take a list of size n, and we will divide it into two lists of size n/2. In each recursive call we will divide the lists into half to calculate the max left, right and middle associated with them. Each recursive call will return the maximum of max left, max right and max left, because as we discussed earlier a maximum subsequence of a sub-list will come in handy when we are looking for the maximum subsequence of the main list.
I think I have discussed about my algorithm enough. So I will share my python code to solve the problem. Where A is our input list.
def MSS(first, last, A):"""Precondition: A is a listPostcondition: max subsequence sum will be returnedfirst is the starting point from list Awhile last is the ending point"""if len(A[first:last+1]) == 0:return 0if len(A[first:last+1]) == 1:return A[first]else:middle = (first + last) // 2last_sum_left = A[middle]temp_sum = 0for i in range(middle, first-1, -1):temp_sum += A[i]if temp_sum > last_sum_left:last_sum_left = temp_sumlast_sum_right = A[middle+1]temp_sum = 0for i in range(middle+1, last):temp_sum += A[i]if temp_sum > last_sum_right:last_sum_right = temp_summax_middle = last_sum_left + last_sum_rightreturn max((MSS(first, middle, A), max_middle, MSS(middle+1, last, A)))
No comments:
Post a Comment