# Split Array Largest Sum

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.

```
#Binary search + Greedy solution
class Solution:
def countPartitions(self, nums, maxSum):
partitions = 1
subSum = 0
for num in nums:
if subSum + num <= maxSum:
subSum += num
else:
partitions += 1
subSum = num
return partitions
def splitArray(self, nums: List[int], k: int) -> int:
low = max(nums)
high = sum(nums)
while low <= high:
mid = (low + high) // 2
partitions = self.countPartitions(nums, mid)
if partitions > k:
low = mid + 1
else:
high = mid - 1
return low
```

This is a canonical binary search problem. It is often phrased in a way where it asks to minimize the weight of shipments and there are a few variations on the same theme.

## Related Problems

Given an array of intervals where intervals[i] = [starti, endi], merge all overlapping intervals, and return *an array of the non-overlapping intervals that cover all the intervals in the input*.

You are given an integer array nums. You are initially positioned at the array's **first index**, and each element in the array represents your maximum jump length at that position.

Return true* if you can reach the last index, or *false* otherwise*.

You are given an array of CPU tasks, each represented by letters A to Z, and a cooling time, n. Each cycle or interval allows the completion of one task. Tasks can be completed in any order, but there's a constraint: **identical** tasks must be separated by at least n intervals due to cooling time.

Return the *minimum number of intervals* required to complete all tasks.

Given an array nums with n integers, your task is to check if it could become non-decreasing by modifying **at most one element**.

We define an array is non-decreasing if nums[i] <= nums[i + 1] holds for every i (**0-based**) such that (0 <= i <= n - 2).