# 410. Split Array Largest Sum

## Problem Statement

<br>

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.

&#x20;

**Example 1:**

<pre><code><strong>Input: nums = [7,2,5,10,8], k = 2
</strong><strong>Output: 18
</strong><strong>Explanation: There are four ways to split nums into two subarrays.
</strong>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.
</code></pre>

**Example 2:**

<pre><code><strong>Input: nums = [1,2,3,4,5], k = 2
</strong><strong>Output: 9
</strong><strong>Explanation: There are four ways to split nums into two subarrays.
</strong>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.
</code></pre>

&#x20;

**Constraints:**

* `1 <= nums.length <= 1000`
* `0 <= nums[i] <= 106`
* `1 <= k <= min(50, nums.length)`

## Intuition

```
Approach:

Try for a range of minSum
Here, we have to minimize the max_sum for various splits

1 2 3 4 5  Let k=2
1 | 2 3 4 5
1 2 | 3 4 5
1 2 3 | 4 5 
1 2 3 4 | 5 

Min split at 9

So, low = max_element , Because, if we take minimum of arr as low
Then, other will not be alloted, or added to sum

high = arr_sum

For each value,
Try to find ,

if k groups are possible

1 2 3 | 4 5

1-> 1 2 3
2-> 4 5

like that


Now if we took low as min
let 1 here
1-> 1
2-> --
so on 
Not allocated to any array
```

### Links

<https://leetcode.com/problems/split-array-largest-sum/description/>

### Video Links

<https://www.youtube.com/watch?v=thUd_WJn6wk&ab_channel=takeUforward>

### Approach 1:

```
Instead we can also return low
```

{% code title="C++" lineNumbers="true" %}

```cpp
class Solution {
public:
    int check_split(vector<int>& arr, int mid){
        int sum = 0;
        int count=1;
        for(auto &it: arr){
            if(sum + it <= mid)
                sum += it;
            else{
                count++;
                sum = it;
            }
        }   

        return count;
    }

    int splitArray(vector<int>& arr, int k) {
        int low=*max_element(arr.begin(), arr.end()); 
        int high=accumulate(arr.begin(), arr.end(), 0);
        int ans;
        while(low <= high){
            int mid = low + (high-low)/2;
            int sum = check_split(arr, mid);

            if(sum > k){
                low = mid+1;
            }
            else{
                ans = mid;
                high = mid-1;
            }
        }

        return low;
    }
};
```

{% endcode %}

### Approach 2:

```
```

{% code title="C++" lineNumbers="true" %}

```cpp
```

{% endcode %}

### Approach 3:

```
```

{% code title="C++" lineNumbers="true" %}

```cpp
```

{% endcode %}

### Approach 4:

```
```

{% code title="C++" lineNumbers="true" %}

```cpp
```

{% endcode %}

### Similar Problems

###