biggest_subsequence(xs): Given a list of int values, there exists some subsequen
ID: 3873140 • Letter: B
Question
biggest_subsequence(xs): Given a list of int values, there exists some subsequence whose sum is the biggest. Return the first and last index of this biggest subsequence. Return None when list is empty. Just like the range function, the start index is included, and the stop index is excluded. o Assume: xs is a list of integers. o Restrictions: no extra restrictions. o biggest-subsequence([10,-18, 6, 7, 8,-1001) o biggest_subsequence ([1,5,-2,-4,5]) o biggest_subsequence(I-5,-2,-4,-13]) o biggest_subsequence([]) (2,5) (e,2) NoneExplanation / Answer
# Note - while copying the code do it properly because indentation may give you an error
# function which calculates subsequence whose sum is biggest
def biggest_subsequence( xs ):
length = len( xs )
# checking whether the list is empty or not
if length == 0:
print("None")
else:
# initalizations
# bigstart and bigend variables contain our final answers
start = -1
end = 0
bigstart = -1
bigend = 0
for x in xs:
# check whether we are at the first element of the list
if start == -1:
sumval = x
end = end + 1
start = start + 1
maxsum = sumval
bigstart = start
bigend = end
else:
# check whether biggest sum of the subsequence ending at the previous
# element is greater than zero
if sumval > 0:
sumval = sumval + x
end = end + 1
# updating the maxsum and corresponding indices
if maxsum < sumval:
maxsum = sumval
bigstart = start
bigend = end
else:
sumval = x
start = end
end = end + 1
# updating the maxsum and corresponding indices
if maxsum < sumval:
maxsum = sumval
bigstart = start
bigend = end
print ("(",bigstart,",",bigend,")")
# main function to test the program
def main():
# list which we are going to pass the above function
xs = [-5,-2,-4,-13]
biggest_subsequence(xs)
if __name__ == "__main__": main()
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.