# DFS+memorization, enhanced Python DP solution, 39-42ms

• This is not necessarily a smart solution, but I did not see anyone use the same method to enhance DP, so I want to discuss this solution.

Obviously, The best answer cannot be smaller than sum(nums) / m. Any subarray with sum smaller than sum(nums) / m will force another subarray with sum larger than it. To get the minimum largest sum, we can constrain the sum of each subarray close to sum(nums) / m.

The recursion here will first find out the smallest subarray nums[:j-1] with sum larger than sum(nums) / m. Then two search branch will be open:

1. consider nums[:j-1] as one of the subarray, recursively split the rest of array, nums[j:]
2. consider nums[:j-2] as one of the subarray, whose sum is also close to sum(nums) / m but smaller. Also recursively split the rest of array, nums[j-1:]

After the split, it is easy to conclude the answer of minimum largest sum.

Use memorization to store the answer of state (m, i)
I also try to prove the boundary of subarray sum is legal, but I still cannot find a strict enough proof. Please point out my mistake if you find any.

class Solution(object):
def splitArray(self, nums, m):
"""
:type nums: List[int]
:type m: int
:rtype: int
"""
avg = sum(nums) / m
mem = {}
return self.dfs(nums, m, avg, mem, 0)

def dfs(self, nums, m, avg, mem, i):
acc = 0
j = i
ret = 0
if mem.has_key((m, i)):
return mem[(m, i)]
if m == 1:
ret = sum(nums[j:])
mem[(m, i)] = ret
return ret
if (len(nums) - j)  <= m:
ret = max(nums[(-1 * m):])
while (len(nums) - j) > m - 1 and acc <= avg:
acc += nums[j]
j += 1
ret = max(acc, self.dfs(nums, m - 1, sum(nums[j:]) / (m - 1), mem, j))
if j - i > 1:
ret = min(ret, max(
acc - nums[j - 1],
self.dfs(nums, m - 1, sum(nums[j-1:]) / (m - 1), mem, j - 1)))
mem[(m, i)] = ret
return ret

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.