> For the complete documentation index, see [llms.txt](https://netjimmy.gitbook.io/code-interview-note/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://netjimmy.gitbook.io/code-interview-note/binary_search/split-array-largest-sum.md).

# Split Array Largest Sum

## 410. Split Array Largest Sum

Given an array which consists of non-negative integers and an integer m, you can split the array into m non-empty continuous subarrays. Write an algorithm to minimize the largest sum among these m subarrays.

```
Input:
nums = [7,2,5,10,8]
m = 2

Output:
18
[7,2,5] and [10,8]
```

#### DP

dp\[i]\[j] = 前 i 個 num 構成 j 個 subarray 的 minimize largest sum

1. 先計算每個index的presum
2. dp\[i]\[j] = min(dp\[i]\[j], max(dp\[k]\[j-1], presum\[i] - presum\[k]))

```python
def splitArray(self, nums: List[int], m: int) -> int:
    n = len(nums)
    
    dp = [[sys.maxsize] * (m+1) for _ in range(n+1)]
    dp[0][0] = 0
    
    accu_sum = [0] * (n+1)
    
    for i, num in enumerate(nums):
        accu_sum[i+1] = accu_sum[i] + num
    
    for i in range(1, n+1):
        for j in range(1, m+1):
            for k in range(0, i):
                dp[i][j] = min(dp[i][j], max(dp[k][j-1], accu_sum[i]-accu_sum[k]))
                
    return dp[n][m]
```

#### Binary Search

1. 利用binary search 找到upperbound
2. 利用 count subarray numbers 作為 left and right 條件

```python
def splitArray(self, nums: List[int], m: int) -> int:
    l = max(nums) 
    r = sum(nums
    ans = r
    while l < r:
        mid = (l+r)//2
        sumUp = 0
        count = 1
        for n in nums:
            if sumUp+n > mid:
                count+=1
                sumUp=n
            else:
                sumUp+=n
                
        if count <= m:
            ans = min(ans, mid)
            r = mid
        else:
            l = mid+1     
    return ans
```

## 1011. Capacity To Ship packages Within D Days

Find the least weight capacity of the ship that will result in all the packages on the conveyor belt being shipped within `D` days.

```python
Input: weights = [1,2,3,4,5,6,7,8,9,10], D = 5
Output: 15
Explanation: 
A ship capacity of 15 is the minimum to ship all the packages in 5 days like this:
1st day: 1, 2, 3, 4, 5
2nd day: 6, 7
3rd day: 8
4th day: 9
5th day: 10
```

Some logic as 410

```python
def shipWithinDays(self, weights: List[int], D: int) -> int:
    left = max(weights)
    right = sum(weights)
    ans = right
    
    while left < right:
        mid = (right+left)//2
        
        sumUp, split = 0, 1
        for n in weights:
            if sumUp+n > mid:
                split+=1
                sumUp = n
            else:
                sumUp+=n
                
        if split > D:
            left = mid+1
        else:
            ans = min(ans, mid)
            right = mid  
    return ans
```

## 774. Minimize Max Distance to Gas Station

On a horizontal number line, we have gas stations at positions `stations[0], stations[1], ..., stations[N-1]`, where `N = stations.length`.

Now, we add `K` more gas stations so that **D**, the maximum distance between adjacent gas stations, is minimized.

Return the smallest possible value of **D**.

```python
Input: stations = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10], K = 9
Output: 0.500000
```

1. `stations.length` will be an integer in range `[10, 2000]`.
2. `stations[i]` will be an integer in range `[0, 10^8]`.
3. `K` will be an integer in range `[1, 10^6]`.
4. Answers within `10^-6` of the true value will be accepted as correct.

```python
 """
Binary Search
找出最大的可能number 0 ~ 10^8
A possible function 利用 利用distance 得到的 gas station 數比較
"""
def minmaxGasDist(self, stations: List[int], K: int) -> float:
    left, right = 0, 10**8
    
    def possible(dis):
        count = 0
        for i in range(len(stations)-1):
            count += (stations[i+1] - stations[i])//dis
        return count <= K
    
    while right - left > 10**-6:
        mid = (right + left)/2
        if possible(mid):
            right = mid
        else:
            left = mid
    return left
```