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


---

# 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://netjimmy.gitbook.io/code-interview-note/binary_search/split-array-largest-sum.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.