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:

- consider
`nums[:j-1]`

as one of the subarray, recursively split the rest of array,`nums[j:]`

- 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
```