We want to split an array in to m segments, and find the minimum value of the max sum of each segment. We can define ok(s) as whether we can split the array into m segments such that the sum each segment is less than or equal to s. We know when s >= sum(nums), ok(s) = true; when s < max(nums), ok(s) = false. In between, i.e. max(nums) <= s < sum(nums), there is some boundary x such that for s < x, ok(s) = false and for s >= x, ok(s) = true. Therefore, we can treat the ok(s) segment as a sorted array, and use binary search to find our target x.

To evaluate ok(s), we can use a greedy approach by taking as many values as we can for each segment. If we can make every segment sum up to less than or equal to s with less than or equal to m segments, then ok(s) is true.

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

def _binarySearch(self, nums, m):
l = max(nums)
r = sum(nums)
# [x, x, ..., x, v, v, ..., v]
while l < r:
print(l, r)
mid = (l + r) // 2
if self._ok(nums, mid, m):
r = mid
else:
l = mid + 1
return l

def _ok(self, nums, maxSum, m):
curSum = 0
thisM = 1
for x in nums:
if curSum + x <= maxSum:
curSum += x
else:
thisM += 1
curSum = x
return thisM <= m