# 410. Split Array Largest Sum
#### Difficulty: Hard
link: https://leetcode.com/problems/split-array-largest-sum/

### 1. Binary Search
#### $O(n\ log\ m)$ runtime, $O(1)$ space
###### n = len(nums), m = sum(nums)

先分析題目，如果要討論所有可能的subarray切法，這是重複組合的問題：把n個物品分成k堆，每一堆至少要有1個物品。

每一堆優先分配ㄧ個物品後，就變成非負整數解問題$X_1+...+X_k=n-k$，總共有$H^k_{n-k}=C^{n-1}_{k-1}$種可能，窮舉所有可能的解法沒辦法在多項式時間內解完，所以要另外想辦法。

改成直接猜一個largest_sum，檢查能否切出k個subarray，每個subarray總和不超過largest_sum，再利用binary search找出滿足這個條件的最小值。

搜尋範圍的下界是max(nums)，也就是k=n的情況；上界是sum(nums)，也就是k=1的情況。

feasible函數的for迴圈從左邊開始，蒐集總和不超過largest_sum的元素為一堆，檢查堆數小於等於k，即為合法。

##### python

class Solution:
    def splitArray(self, nums: List[int], k: int) -> int:
        def feasible(largest_sum):
            total = 0
            count = 0
            for num in nums:
                total += num
                if total > largest_sum:
                    count += 1
                    total = num
            
            return count + 1 <= k
        
        left, right = max(nums), sum(nums)
        
        while left < right:
            mid = left + (right - left) // 2
            if feasible(mid):
                right = mid
            else:
                left = mid + 1
        
        return left

###### tags: `leetcode`