# Split Array Largest Sum(二分，dp？）

Given an array which consists of non-negative integers and an integerm, you can split the array intomnon-empty continuous subarrays. Write an algorithm to minimize the largest sum among thesemsubarrays.

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

分析：

看成找一个target，使得分成的m个subarray的sum都<=target，所以用二分，这个target在max(nums)和sum(nums）之间。在这个区间左右移动算是已排序数组。

辅助函数中cnt是切下去的刀数。刀数+1 = group数目

这里二分不知道边界怎么做了

```
class Solution:
    def splitArray(self, nums, m):
        """
        :type nums: List[int]
        :type m: int
        :rtype: int
        """
        l = max(nums)
        r = sum(nums)
        if m == 1:
            return r

        while l < r:
            mid = (l+r)//2
            if self.valid(nums, m, mid):
                r = mid
            else:
                l = mid+1
        return r

    def valid(self,nums,m,target):
        cnt = 0
        summ = 0
        for num in nums:
            summ += num
            if summ > target:
                summ = num
                cnt += 1
                if cnt + 1 > m:
                     return False

        return True
```

dp：前面j组和i结尾，然后j,i之间开始切分最后一组。有点类似背包最后一个value开分。

Python可以 python3不行

```
class Solution(object):

    def splitArray(self, nums, m):
        if not nums or not m or len(nums) < m:
            return
        n = len(nums)
        f = [float('inf')]*(n+1)
        presum = [0]*(n+1)
        for i,v in enumerate(nums):
            presum[i+1] = presum[i]+v

        f[0]=0
        for i in range(m):
            for j in range(n,0,-1): #1->n
                for k in range(i-1,j):
                    f[j]=min(f[j],max(f[k],presum[j]-presum[k]))

        return f[n]
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://nataliekung.gitbook.io/ladder_code/facebook/split-array-largest-sumer-fen-ff0c-dp.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.