Split Array Largest Sum
Programming Interview
Hard
5 views
Problem Description
You're given {x}. Split array into m non-empty continuous parts to minimize the maximum part sum. Output that minimum possible value.
Input Format
First line n m. Second line n integers.
Output Format
One integer answer.
Official Solution
import sys
p=sys.stdin.read().strip().split()
if len(p)<2: sys.exit(0)
it=iter(p)
n=int(next(it)); m=int(next(it))
a=[int(next(it)) for _ in range(n)]
lo=max(a)
hi=sum(a)
def can(limit):
parts=1
s=0
for v in a:
if s+v<=limit:
s+=v
else:
parts+=1
s=v
if parts>m:
return False
return True
while lo<hi:
mid=(lo+hi)//2
if can(mid):
hi=mid
else:
lo=mid+1
sys.stdout.write(str(lo))
Solutions (0)
No solutions submitted yet. Be the first!
No comments yet. Start the discussion!