410. Split Array Largest Sum
Đề Bài
Given an integer array nums and an integer k, split nums into k non-empty subarrays such that the largest sum of any subarray is minimized.
Return the minimized largest sum of the split.
A subarray is a contiguous part of the array.
Example 1:
Input: nums = [7,2,5,10,8], k = 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.
Example 2:
Input: nums = [1,2,3,4,5], k = 2 Output: 9 Explanation: There are four ways to split nums into two subarrays. The best way is to split it into [1,2,3] and [4,5], where the largest sum among the two subarrays is only 9.
Constraints:
1 <= nums.length <= 10000 <= nums[i] <= 1061 <= k <= min(50, nums.length)
Thuật Toán & Kỹ Thuật
⏱️ Thời gian
O(n)
💾 Không gian
O(n)
Lời Giải
Python
0410-split-array-largest-sum.py
class Solution:
def splitArray(self, nums: List[int], k: int) -> int:
def trimNums(target: int) -> int:
cnt = 1
total = 0
for num in nums:
if total + num <= target:
total += num
else:
cnt += 1
total = num
return cnt
l, r, ans = max(nums), sum(nums), inf
while l <= r:
m = (l + r) >> 1
if trimNums(m) <= k:
ans = min(ans, m)
r = m - 1
else:
l = m + 1
return ans