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.