# LeetCode: 410. 分割数组的最大值¶

## 1、题目描述¶

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

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

18



## 2、解题思路¶

• 深度优先加二分法
• 首先计算出平均分成m份的平均为多少，每次使用二分法，尽可能取到平均值以及前后的值
from itertools import accumulate
from functools import lru_cache
import bisect

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

acc_sums = [0] + list(accumulate(nums))
average = acc_sums[-1] / m

@lru_cache(None)
def dfs(pos, k):
if k == 1:
return acc_sums[length] - acc_sums[pos]
ans = float('inf')
target = acc_sums[pos] + average
index = bisect.bisect_left(acc_sums, target, pos + 1)

# for i in range(pos, index+1 if index+1 <= length - k + 1 else length - k + 1):
#     ans = min(ans, max(acc_sums[i + 1] - acc_sums[pos], dfs(i + 1, k - 1)))

if index > pos + 1:
ans = min(ans, max(acc_sums[index - 1] - acc_sums[pos], dfs(index - 1, k - 1)))
if index <= length - k + 1:
ans = min(ans, max(acc_sums[index] - acc_sums[pos], dfs(index, k - 1)))
if index + 1 <= length - k + 1:
ans = min(ans, max(acc_sums[index + 1] - acc_sums[pos], dfs(index + 1, k - 1)))
return ans

return dfs(0, m)

• 和值二分法

• 最小的值就是数组中最大的数字，最大值就是数组之和

• 使用二分法不断逼近，每次尝试用中间值去划分数组，划分数量太少，表示和值需要减少，划分数量太多，表示需要增大和值
class Solution:
def splitArray(self, nums: List[int], m: int) -> int:

def get_groups(current_sum):
res = 1
temp_sum = 0
for num in nums:
temp_sum += num
if temp_sum > current_sum:
temp_sum = num
res += 1
return res

left, right = max(nums), sum(nums)
while left <= right:
mid = left + (right-left) // 2
if get_groups(mid) > m:
left = mid + 1
else:
right = mid - 1
return left