# 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

###


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://coding-9.gitbook.io/untitled/binary-search/bs-over-answer-space-answer-space/410.-split-array-largest-sum.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.