Split Array Largest Sum

Split Array Largest Sum

Hard Programming Interview Data Structures 15 views
Explanation Complexity

Problem Statement

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.

Example

5 2
7 2 5 10 8
18

Constraints

1

Input / Output Format

Input Format
First line n m. Second line n integers.
Output Format
One integer answer.
Constraints
1

Examples

Input:
5 2 7 2 5 10 8
Output:
18

Example Solution (Public)

Programming Interview 
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))

Official Solution Code

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))
Please login to submit solutions.
Editor
Output

                                        

                                    

                                    

                                        

                                                                                    
Please login to submit solutions.