Given an array ,divide this array into k possible subsets and find the maximum sum of these subsets ,and from these sum find the minimum among all? How to approach this problem?
The question was kind of unclear, and heres why-
You have to divide the array into k subsets, right? Then just sort the array, make k-1 subset of first k-1 element (size=1 for each subset) and one final subset consisting of remainder of array.
Minimum sum of elements in a subset =minimum element.
But I think it will be on lines of minimum subset of size p or some other constraint added as well, else the method I described above should work.
EDIT:
I can think of a rough algo, but cannot guarantee the correctness.
It goes around that, you sort the array in ascending order, make k-1 subsets from last k-1 greatest element, and 1 subset of all small elements in start. I feel that the subset with maximum sum in this arrangement should be the answer.
Proof-
Consider 2 cases- The subset of size>1 formed by smaller elements in sum has-
a) Greatest sum
b) Not Greatest sum
If a) holds, we are done. We can see that we cannot get a lower answer than this.
If b) holds, then look at the subset with largest sum. This is the least sum of that subset since the size is 1. Other arrangements will only increase the elements and hence sum of this. Hence, if all elements are >=0 , we can say that this subset should be our answer.
I cant think of a dp solution to it, sorry for that. Do tell if this helps you in any way. 
But how is this related to given problem? Can u explain it further?
let us say we have array[]={1,2,3} and k=2;
then the possible subsets are[{1},{2,3}],[{2},{1,3}],[{3},{1,2}];
here the maximum sum in 1st case i.e in[{1},{2,3}] is 5.
Similarly for 2nd case it is 4 ,in 3rd case it is 3 ,Now the minimum among all these is 3.
Constraints for k? And link to problem if its available online.
1 Like
@beginner_1111 constraints on size of the array would be helpful!
Also just to be sure, the subsets need not be contiguous? Otherwise it is the same as this problem MINMAXTF
@vijju123 
it seems that logic is not correct .Consider A=[1,2,3,4] and k=2.
According to u the answer should be 6([{1,2,3},{4}]). But consider this partition [{1,4},{2,3}] ,the max sum is 5 and it is smaller than 6 so answer should be 5.
Good work though:)