1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
|
// 410. Split Array Largest Sum
#include "leetcode.h"
/*
* 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 minimised.
* return the minimised largest sum of the split. a subarray is a contiguous
* part of the array
*/
int splitArray(int *nums, int numsSize, int k) {
int right = 0, left = 0;
for (int i = 0; i < numsSize; i++) {
left = left > nums[i] ? left : nums[i];
right += nums[i];
}
right++;
while (left < right) {
int mid = (left + right) / 2, cnt = 1, tmp = 0;
for (int i = 0; i < numsSize; i++)
if (tmp + nums[i] > mid) {
cnt++;
tmp = nums[i];
} else {
tmp += nums[i];
}
if (cnt > k)
left = mid + 1;
else
right = mid;
}
return (int)left;
}
int main() {
int n1[] = {7, 2, 5, 10, 8}, n2[] = {1, 2, 3, 4, 5};
printf("%d\n", splitArray(n1, ARRAY_SIZE(n1), 2)); // expect: 18
printf("%d\n", splitArray(n2, ARRAY_SIZE(n2), 2)); // expect: 9
}
|