$(25$ pts$)$ Given an array $A[1..n]$ of positive integers and an integer $mn,$ we want to split A into at most $m$ non$-$empty contiguous subarrays so that the largest sum among these subarrays is minimized. Design an algorithm based on a greedy strategy to solve this problem. Analyze the running time of your algorithm. Explain the correctness of your algorithm.

For example, if the array is $A=[7,2,5,10,8]$ and $m=2,$ there are several ways to split $A$ : $,([7,2,5],[10,8]),$ and $([7,2,5,10],[8]).$ The best way is $([7,2,5],[10,8])$ because the maximum sum is $10+8=18$ which is the minimum among all possible ways of splitting.

Hint: You need to invoke a greedy algorithm multiple times. How many times?

$(25$ pts$)$ Given an array $A[1..n]$ of positive integers and an integer $mn,$ we want to split A into at most $m$ non$-$empty contiguous subarrays so that the largest sum among these subarrays is minimized. Design an algorithm based on a greedy strategy to solve this problem. Analyze the running time of your algorithm. Explain the correctness of your algorithm.

For example, if the array is $A=[7,2,5,10,8]$ and $m=2,$ there are several ways to split $A$ : $,([7,2,5],[10,8]),$ and $([7,2,5,10],[8]).$ The best way is $([7,2,5],[10,8])$ because the maximum sum is $10+8=18$ which is the minimum among all possible ways of splitting.

Hint: You need to invoke a greedy algorithm multiple times. How many times?