Problem 1 [60 pts] Write code in Python for the following problem: Given a list of numbers, any of which may be positive, negative or zero, write a divide-and-conquer algorithm to compute the maximum possible sum of numbers which occur as a contiguous subarray. If all numbers are negative for example, the output is the empty sum which is zero. If the input is,

10, 0, -1, 0, 0, 2, 2 the answer is 13.

If the input is, 5,-6,1,1,4

the answer is 6.

Also mention, as a comment in the code the runtime of your algorithm.

For example, if your analysis comes out quadratic time you could say: #The runtime is O(n^2) where n is the length of the list.

Problem 1 [60 pts) Write code in Python for the following problem: Given a list of numbers, any of which may be positive, negative or zero, write a divide-and-conquer algorithm to compute the maximum possible sum of numbers which occur as a contiguous subarray. If all numbers are negative for example, the output is the "empty sum which is zero. If the input is, 10, 0, -1, 0, 0, 2, 2 the answer is 13. If the input is, 5,-6,1,1,4 the answer is 6. Also mention, as a comment in the code the runtime of your algorithm. For example, if your analysis comes out quadratic time you could say: #The runtime is O(n^2) where n is the length of the list