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]))

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 條件

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.

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

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.

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.

 """
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