## Algorithm

Problem Name: 410. 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.

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 <= 1000`
• `0 <= nums[i] <= 106`
• `1 <= k <= min(50, nums.length)`

## Code Examples

### #1 Code Example with C Programming

```Code - C Programming```

``````
#define ROW 1000
#define COL 51

long split(int *nums, int sz, int start, int m, long sum[ROW], long dp[ROW][COL]) {
int i;
long k, k1, k2;
unsigned long min = -1;

if (m == 1) return sum[start]; // sum of nums[start...end]

if (dp[start][m] != -1) return dp[start][m];

k1 = 0;
for (i = start; i  < = sz - m; i ++) {
k1 += nums[i];                                  // first half
k2 = split(nums, sz, i + 1, m - 1, sum, dp);    // second half
k = k1 > k2 ? k1 : k2;                          // max of first and second
if (min > k) min = k;                           // min of all possible cuts
}
dp[start][m] = min;

return min;
}
int splitArray(int* nums, int numsSize, int m) {

long sum[ROW], dp[ROW][COL], k;
int i;

k = 0;
for (i = numsSize - 1; i >= 0; i --) {
k += nums[i];
sum[i] = k;
}

memset(dp, -1, ROW * COL * sizeof(dp[0][0]));

return split(nums, numsSize, 0, m, sum, dp);;
}
``````
Copy The Code &

Input

cmd
nums = [7,2,5,10,8], k = 2

Output

cmd
18

### #2 Code Example with Javascript Programming

```Code - Javascript Programming```

``````
const splitArray = (nums, m) => {
let max = -Infinity, sum = 0
for(let num of nums) {
sum += num
max = Math.max(max, num)
}
if (m === 1) return sum
let l = max, r = sum
while(l < r) {
let mid = l + ((r - l) >> 1)
if(valid(mid, nums, m)) {
r = mid
} else {
l = mid + 1
}
}
return l
}

function valid(target, nums, m) {
let cnt = 1, sum = 0
for(let num of nums) {
sum += num
if(sum > target) {
cnt++
sum = num
if(cnt > m) return false
}
}

return true
}
``````
Copy The Code &

Input

cmd
nums = [7,2,5,10,8], k = 2

Output

cmd
18

### #3 Code Example with Python Programming

```Code - Python Programming```

``````
class Solution:
def splitArray(self, nums, m):
def valid(mid):
cnt = sm = 0
for num in nums:
sm += num
if sm > mid:
cnt += 1
if cnt>= m: return False
sm = num
return True
l, h = max(nums), sum(nums)
while l < h:
mid = (l + h) // 2
if valid(mid):
h = mid
else:
l = mid + 1
return l
``````
Copy The Code &

Input

cmd
nums = [1,2,3,4,5], k = 2

Output

cmd
9

### #4 Code Example with C# Programming

```Code - C# Programming```

``````
using System;

namespace LeetCode
{
public class _0410_SplitArrayLargestSum
{
public int SplitArray(int[] nums, int m)
{
var largestNumber = 0;
var total = 0;
for (int i = 0; i  <  nums.Length; i++)
{
largestNumber = Math.Max(nums[i], largestNumber);
total += nums[i];
}

var l = largestNumber;
var h = total;
while (l  < = h)
{
var mid = l + (h - l) / 2;
var count = 1;
var currentSum = 0;
for (var i = 0; i  <  nums.Length; i++)
{
if (currentSum + nums[i] > mid)
{
count++;
if (count > m) break;
currentSum = nums[i];
}
else
currentSum += nums[i];
}
if (count  < = m)
h = mid - 1;
else
l = mid + 1;
}
return l;
}
}
}
``````
Copy The Code &

Input

cmd
nums = [1,2,3,4,5], k = 2

Output

cmd
9