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 parti$-$

tioning 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.$

$[$