Example 1:
Input Format: N = 5, a[] = {1,2,3,4,5}, k = 3
Result: 6
Explanation: There are many ways to split the array a[] into k consecutive subarrays. The best way to do this is to split the array a[] into [1, 2, 3], [4], and [5], where the largest sum among the three subarrays is only 6.

Example 2:
Input Format: N = 3, a[] = {3,5,1}, k = 3
Result: 5
Explanation: There is only one way to split the array a[] into 3 subarrays, i.e., [3], [5], and [1]. The largest sum among these subarrays is 5.

Disclaimer: Here is the practice link to help you assess your knowledge better. It's highly recommend trying to solve it before looking at the solution.

Brute Force

Algorithm

First, we will find the maximum element and the summation of the given array.
We will use a loop to check all possible answers from max(arr[]) to sum(arr[]).
Next, inside the loop, we will send ‘maxSum’, to the function countPartitions() function to get the number of partitions.
The first value of ‘maxSum’, for which the number of partitions will be equal to ‘k’, will be our answer. So, we will return that particular value of ‘maxSum’.
Finally, if we are out of the loop, we will return max(arr[]) as there cannot exist any answer smaller than that.

Code