×

# To divide an array into k segments such that the minimum of the segments is the maximum

 0 1 Given an array of n elements divide the elements into k segments such that the minimum sum of each of the segments is maximum eg array is 10 5 8 7 and k is 2 the different ways to divide the array into two segment is (10) , (5,8,7) min sum is 10 (10,5) (8,7) min sum is 15 (10,5,8) (7) min sum is 7 so the max of the minimum is 15 (7<10<15) 1< n , k < 10^5 how to attain the solution in O(n) or O(nlog n ) asked 26 Jul '17, 13:19 3★athulpai 17●5 accept rate: 0% I hope this isnt related to an on going contest. (26 Jul '17, 16:31)

 0 this can be done using binary search+greedy Here link is a similar question and my solution link comment if you have any doubt. answered 26 Jul '17, 15:43 1.7k●2●10 accept rate: 14%
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×1,768
×1,664
×1,056
×75
×68
×68

question asked: 26 Jul '17, 13:19

question was seen: 2,312 times

last updated: 26 Jul '17, 16:31