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 <= 10000 <= nums[i] <= 1061 <= 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);;
}
Input
nums = [7,2,5,10,8], k = 2
Output
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
}
Input
nums = [7,2,5,10,8], k = 2
Output
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
Input
nums = [1,2,3,4,5], k = 2
Output
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;
}
}
}
Input
nums = [1,2,3,4,5], k = 2
Output
9