write a Python program that takes as input a list of daily prots of a company an
ID: 672315 • Letter: W
Question
write a Python program that takes as input a list of daily prots of
a company and determine the maximum total amount that the company can make in consecutive
days. A daily prot can be a negative number, which means the company loses money that day
I wrote this program
#returns the maximum interval in the provided list
#It will retun an list of l, r, and the sume of l to r
def findMax(list):
#max starts at 0
max =0
#the interval starts at 0
l=0
r=0
for x in range(len(list)):
for y in range(len(list)):
temp = sum(list[x:y+1])
if temp > max:
max = temp
l=x
r=y
return [l,r,sum(list[l:r])]
print (findMax([-1,4,3,-7,4,5,6,-2,6,5,34]))
My teacher said it did not work, and How would I make it divide and conquer so it is below n^2
Explanation / Answer
def findMax(productPrice):
current_max = productPrice[0]
max_so_far = productPrice[0]
for i in range(1,len(productPrice)):
current_max = max(productPrice[i],current_max+productPrice[i])
max_so_far = max(max_so_far,current_max)
return max_so_far
print findMax([-1,4,3,-7,4,5,6,-2,6,5,34])
Paradigm : Dynamic Programming
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.