Given an array of arbitrary integers of length $n,$ we want to determine the maximum sum of a contiguous sequence of numbers within the array. For example, in the array

$5-756-12-102$

the answer is $12$:$5+6-1+2$

$(5$ pts$)$ For an array that is already known to contain only positive integers, provide a linear time algorithm for answering this question and state its complexity.

$(20$ pts$)$ Devise a divide$-$and$-$conquer algorithm for solving this problem in the general case $($positive and negative integers$),$ and prove its time complexity bounds. No points will be awarded for an algorithm that does not use the divide and conquer approach, even if it is correct.