COMPLETE THE FOLLOWING PROGRAM IN PYTHON:

STARTER CODE:

def slowslicesum(L): return max((sum(L[i:j]), i, j) for j in range(len(L)+1) for i in range(j))

def quadraticslicesum(L): P = [sum(L[:i]) for i in range(len(L) + 1)] sums = [] for j in range(len(L) + 1): for i in range(j+1): sums.append((P[j] - P[i], i, j)) return max(sums)

Finding the biggest slice Your goal is to find the slice of a list that has the largest sum. You will find both the largest sum as well as the indices starting and ending the slice. That is, if L[3:9] is the largest slice and the sum of the elements is 500 , you will return the tuple (500, 3, 9) . Call your function slicesum and put it in a file called sucesum. . Recall the standard python convention that slices L [start: end] start at start and go up to but not including end First, a short and slow solution It's often useful to just get something working at first. In this case, it's possible to just try every slice, sum its elements, and find the max. def slowslicesum (L) return max((sum(L[i:j]), i, j) for j in range(len (L)+1) for i in range (j)) # Let's try it a couple times to see. print (slowslicesum ([-1, 2, 3, -1])) print (slowslicesum([-1, 2, 3, -1, 4, -10])) Like a lot of one-liners, there's a lot in there. Let's break it down for practice understanding such expressions. It is taking the max of the sum of a slice for all possible slices of the list. We could have written it out more explicitly, as follows def longs lows licesum(L) sums[] forj in range(len(L)+1): for i in range (j): sums . append ( (sum ( L [isj]), i, j)) return max (sums) You should be able to recognize that this function takes O(n3) time. That's pretty bad. It's not too hard to get it down to O(n time by precomputing the sums of some slices. Finding the biggest slice Your goal is to find the slice of a list that has the largest sum. You will find both the largest sum as well as the indices starting and ending the slice. That is, if L[3:9] is the largest slice and the sum of the elements is 500 , you will return the tuple (500, 3, 9) . Call your function slicesum and put it in a file called sucesum. . Recall the standard python convention that slices L [start: end] start at start and go up to but not including end First, a short and slow solution It's often useful to just get something working at first. In this case, it's possible to just try every slice, sum its elements, and find the max. def slowslicesum (L) return max((sum(L[i:j]), i, j) for j in range(len (L)+1) for i in range (j)) # Let's try it a couple times to see. print (slowslicesum ([-1, 2, 3, -1])) print (slowslicesum([-1, 2, 3, -1, 4, -10])) Like a lot of one-liners, there's a lot in there. Let's break it down for practice understanding such expressions. It is taking the max of the sum of a slice for all possible slices of the list. We could have written it out more explicitly, as follows def longs lows licesum(L) sums[] forj in range(len(L)+1): for i in range (j): sums . append ( (sum ( L [isj]), i, j)) return max (sums) You should be able to recognize that this function takes O(n3) time. That's pretty bad. It's not too hard to get it down to O(n time by precomputing the sums of some slices