I have no problem with number 4. I\'m just trying to explain number 5 correctly.
ID: 3604461 • Letter: I
Question
I have no problem with number 4. I'm just trying to explain number 5 correctly. My gut intuition is telling me that when you split A into two halves, the running time is reduced since you've taken "n" (list A) and divided it by 2 (n/2). When placed into a Master's Theorem or using Substitution to find running time, one would find the solution in problem 4 runs in less time compared to the solution in problem 1, which was a straightforward strategy of just keeping up with all "possible intervals."
(20 Points) Write a Python function that takes as input a list A (containing n numbers) and returns the maximum sum of consecutive numbers in the list. For example, if A the output is 70. 4. [10, -50, 40, 20, -10, 20,-10, 5], then This problem is exactly like problem 1. However, you will implement a different strategy: First, break A in 2 halves. Compute the max sum of the left half, the right half. Then, use the functions you implemented in problems 2 and 3, to compute the max sum of A. 5. (10 Points) Explain why the solution of problem 4 is faster than the solution of problem 1.Explanation / Answer
above program procedure :
1.Divide the array in two parts (I have written generic function for it,so later on if you want to divide it into multiple parts you have to simple change the input parameter equals to no of parts.
2.Finding the max sum form both the list
3.Adding the max of both the array and printing the result.
Here is my code :
# function for dividing array into two halfs
def DivideArray(Arr, num):
avg = len(Arr) / float(num)
outArr = []
last = 0.0
while last < len(Arr):
outArr.append(Arr[int(last):int(last + avg)])
last += avg
return outArr
# Find the largest sum of consecutive numbers
def MaxConSum(array):
maxSom = maxUpToHere = 0
for element in array:
maxUpToHere= max(maxUpToHere + element, 0)
maxSom = max(maxSom, maxUpToHere)
return maxSom
# input array
arr=[10,-50,40,20,-10,20,-10,5]
# print the name along with Hello
dividedArr=[]
dividedArr=DivideArray(arr,2)
print(dividedArr)
# Assigning the first part max sum to variable FirstpartMax
FirstpartMax=MaxConSum(dividedArr[0])
# Assigning the Second part max sum to variable SecondpartMax
SecondpartMax=MaxConSum(dividedArr[1])
# print the result
print(FirstpartMax+SecondpartMax)