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.

Source: leetcode | Difficulty: MEDIUM_HARD
Tags: Dynamic programming

Sorting

Data structures

Greedy algorithms

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

Solutions:
class Solution:

	def splitArray(self, nums, m):
		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
		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:
				start = end - 1
				count += 1
			end += 1
		if accum[-1] - accum[start] > maxx:
			count += 2
		else:
			count += 1
		if end != N or count > m:
			return False
		return True


class Solution:

	def splitArray(self, pages, k):
		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):
		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):

		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):
		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):
		_sum = sum(nums)
		avg = _sum / m
		self.result = 10 ** 10
		n = len(nums)
		cache = {}

		def recur(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
			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)
		return x


class Solution:

	def splitArray(self, nums, m):
		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