Given a sorted list $T$ of $n$ integers and an integer $k,$ we want to partition $T$ into $k$ contiguous segments such that every element of $T$ is in a segment, and the maximum sum of elements in any segment is minimal. For example, if $T=[100,200,300,400,500]$ and $k=2,$ then the best partitioning is $100,200,300$ for the first segment and $400,500$ for the second segment because it leads to a sum of $600$ in the first and $900$ in the second. There isn't a way to partition $T$ so that the sum of elements in each segment is less than $900.$

$($a$)$ Find lower and upper bounds for the maximum sum of elements in a segment in any partitioning of $T.$ You may assume that every integer in $T$ is less than some integer $N.$

$($b$)$ Give an algorithm which determines whether $T$ can be partitioned into $k$ contiguous segments such that the sum of elements in each segment is less than some constant $c.$

$($c$)$ Combine your solutions from parts $($a$)$ and $($b$)$ to design a divide and conquer algorithm which finds an optimal partitioning of $T.$

$[$

$($d$)$ Analyze the running time of your algorithm.