diff options
Diffstat (limited to 'split_array_largest_sum.c')
-rw-r--r-- | split_array_largest_sum.c | 39 |
1 files changed, 39 insertions, 0 deletions
diff --git a/split_array_largest_sum.c b/split_array_largest_sum.c new file mode 100644 index 0000000..09c0331 --- /dev/null +++ b/split_array_largest_sum.c @@ -0,0 +1,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 +} |