Given an array which consists of non-negative integers and an integer m, you can split the array into m non-empty continuous subarrays. Write an algorithm to minimize the largest sum among these m subarrays.


Note:
If n is the length of array, assume the following constraints are satisfied:

1 ≤ n ≤ 1000
1 ≤ m ≤ min(50, n)



Examples: 

Input:
nums = [7,2,5,10,8]
m = 2

Output:
18

Explanation:
There are four ways to split nums into two subarrays.
The best way is to split it into [7,2,5] and [10,8],
where the largest sum among the two subarrays is only 18.

Difficulty: interview

Starter code:

class Solution:
    def splitArray(self, nums: List[int], m: int) -> int:
        

Solutions:
class Solution:
     def splitArray(self, nums, m):
         """
         :type nums: List[int]
         :type m: int
         :rtype: int
         """
         accum = [0]
         N = len(nums)
         mmm = max(nums)
         if m >= N:
             return mmm
         res = 0
         for i in nums:
             res += i
             accum.append(res)
         lower, upper = mmm , sum(nums)
         while lower < upper:
             mid = (lower + upper) // 2
             if not self.isSplitable(accum, m, mid):
                 lower = mid + 1
             else:
                 upper = mid
         # print(lower, upper)
         return upper
     def isSplitable(self, accum, m, maxx):
         start = 0
         N = len(accum)
         end = 0
         count = 0
         while end < N and count < m:
             if accum[end] - accum[start] > maxx:
                 # print('start: ', start, 'end:', end, 'sum', accum[end - 1] - accum[start])
                 start = end - 1
                 count += 1
             end += 1
             #print (count, end)
         if accum[-1] - accum[start] > maxx: #收尾
             count += 2
         else:
             count += 1
         # print('start: ', start, 'end:', end, 'sum', accum[end - 1] - accum[start])
         # print (end, count)
         if end != N or count > m:
             return False
         return True

class Solution:
     def splitArray(self, pages, k):
         """
         :type nums: List[int]
         :type m: int
         :rtype: int
         """
         if not pages or k == 0:
             return 0
 
         pre = sums = [0] + pages[:]
         for i in range(1, len(sums)):
             sums[i] += sums[i-1]
 
         for n in range(2, k + 1):
             if n > len(pages):
                 break
 
             cur = [sys.maxsize] * len(pre)
             i, j = n - 1, n
             while j < len(pre):
                 left, right = pre[i], sums[j] - sums[i]
                 cur[j] = min(cur[j], max(left, right))
                 if i + 1 < j and max(pre[i+1], sums[j] - sums[i+1]) < cur[j]:
                     i += 1
                 else:
                     j += 1
 
             pre = cur
 
         return pre[-1]


class Solution:
     def splitArray(self, nums, m):
         """
         :type nums: List[int]
         :type m: int
         :rtype: int
         """
         pre = sums = [0] + nums
         for i in range(2, len(sums)):
             sums[i] += sums[i-1]
     
         for k in range(2, m + 1):
             i, j, cur = k - 1, k, [sys.maxsize] * len(pre)
             while j < len(pre):
                 left, right = pre[i], sums[j] - sums[i]
                 cur[j] = min(cur[j], max(left, right))
                 if i + 1 < j and max(pre[i+1], sums[j] - sums[i+1]) < cur[j]:
                     i += 1
                 else:
                     j += 1
             pre = cur
 
         return pre[-1]

class Solution(object):
     def splitArray(self, nums, m):
         """
         :type nums: List[int]
         :type m: int
         :rtype: int
         """
         def valid(mid):
             cnt = 0
             current = 0
             for n in nums:
                 current += n
                 if current>mid:
                     cnt += 1
                     if cnt>=m:
                         return False
                     current = n
             return True
 
         l = max(nums)
         h = sum(nums)
 
         while l<h:
             mid = l+(h-l)/2
             if valid(mid):
                 h = mid
             else:
                 l = mid+1
         return int(l)

class Solution:
     def splitArray(self, nums, m):
         """
         :type nums: List[int]
         :type m: int
         :rtype: int
         """
         def valid(mid):
             cnt = 0
             current = 0
             for n in nums:
                 current += n
                 if current>mid:
                     cnt += 1
                     if cnt>=m:
                         return False
                     current = n
             return True
 
         l = max(nums)
         h = sum(nums)
 
         while l<h:
             mid = l+(h-l)/2
             if valid(mid):
                 h = mid
             else:
                 l = mid+1
         return int(l)

class Solution:
     
     def soln_exists(self, nums, m, i):
         index = 0
         for x in range(m):
             total = 0
             while True:
                 total += nums[index]
                 index += 1
                 if (total > i):
                     break
                 if index == len(nums):
                     return True
             index -= 1
         return False
     
     def splitArray(self, nums, m):
         """
         :type nums: List[int]
         :type m: int
         :rtype: int
         """
         work = 1
         while not self.soln_exists(nums, m, work):
             work *= 2
         not_work = work / 2
         while not_work < work - 1:
             middle = not_work / 2 + work / 2
             if self.soln_exists(nums, m, middle):
                 work = middle
             else:
                 not_work = middle
         return int(work)

class Solution:
     def splitArray(self, nums, m):
         """
         :type nums: List[int]
         :type m: int
         :rtype: int
         """
         _sum = sum(nums)
         avg = _sum / m
         self.result = 10**10
         n = len(nums)
         cache = {}
         def recur(idx, m):
             # print(idx,m)
             if idx == n:
                 return 0
             if m == 0:
                 return 10**10
             if (idx, m) in cache:
                 return cache[(idx, m)]
             _sum = 0
             result = 10**10
             i = idx##bugged 
             while i < n :
                 _sum+=nums[i]
                 if i == n - 1 or (_sum + nums[i+1] > avg):
                     tmp = recur(i+1, m - 1)
                     result = min(result, max(tmp, _sum))
                     if _sum > tmp:
                         cache[(idx, m)] = result
                         return result
                 i+=1
             cache[(idx, m)] = result
             return result
         
         x = recur(0,m)
         # print(cache)
         return x
                 
                 
             
             
         
         
         
         
         
         
         


class Solution:
     def splitArray(self, nums, m):
         """
         :type nums: List[int]
         :type m: int
         :rtype: int
         """
         return self.use_binary_search(nums, m)
     
     def use_binary_search(self, nums, m):
         lo, hi = max(nums), sum(nums)
         
         while lo < hi:
             mid = lo + (hi - lo) // 2
             
             if self.valid(mid, nums, m):
                 hi = mid
             else:
                 lo = mid + 1
         return lo
     
     def valid(self, target, nums, m):
         total, count = 0, 1
         for num in nums:
             total += num
             if total > target:
                 total = num
                 count += 1
                 if count > m:
                     return False
         return True


class Solution:
     
     def soln_exists(self, nums, m, i):
         index = 0
         for x in range(m):
             total = 0
             while True:
                 total += nums[index]
                 index += 1
                 if (total > i):
                     break
                 if index == len(nums):
                     return True
             index -= 1
         return False
     
     def splitArray(self, nums, m):
         """
         :type nums: List[int]
         :type m: int
         :rtype: int
         """
         work = 1
         while not self.soln_exists(nums, m, work):
             work *= 2
         not_work = work / 2
         while not_work < work - 1:
             middle = not_work / 2 + work / 2
             if self.soln_exists(nums, m, middle):
                 work = middle
             else:
                 not_work = middle
         return int(work)

class Solution:
     
     def soln_exists(self, nums, m, i):
         index = 0
         for x in range(m):
             total = 0
             while True:
                 total += nums[index]
                 index += 1
                 if (total > i):
                     break
                 if index == len(nums):
                     return True
             index -= 1
         return False
     
     def splitArray(self, nums, m):
         """
         :type nums: List[int]
         :type m: int
         :rtype: int
         """
         work = 1
         while not self.soln_exists(nums, m, work):
             work *= 2
         not_work = work / 2
         while not_work < work - 1:
             middle = not_work / 2 + work / 2
             if self.soln_exists(nums, m, middle):
                 work = middle
             else:
                 not_work = middle
         return int(work)