diff options
-rw-r--r-- | split_array_largest_sum.c | 39 | ||||
-rw-r--r-- | split_array_largest_sum.py | 48 |
2 files changed, 87 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 +} diff --git a/split_array_largest_sum.py b/split_array_largest_sum.py new file mode 100644 index 0000000..8036109 --- /dev/null +++ b/split_array_largest_sum.py @@ -0,0 +1,48 @@ +# 410. Split Array Largest Sum +from collections import defaultdict + +""" +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 +""" + + +class Solution(object): + def helper(self, i, nums, k, cache, cnt): + if i == len(nums): + return 0 + elif k == 1: + return sum(nums[i:]) + else: + if i in cache and k in cache[i]: + return cache[i][k] + cache[i][k] = float("inf") + for j in range(1, len(nums) + 1): + left, right = ( + cnt[i + j] - cnt[i], + self.helper(i + j, nums, k - 1, cache, cnt), + ) + cache[i][k] = min(cache[i][k], max(left, right)) + if left > right: + break + return cache[i][k] + + def splitArray(self, nums, k): + """ + :type nums: List[int] + :type k: int + :rtype: int + """ + cnt = [0] + for i in nums: + cnt.append(cnt[-1] + i) + cache = defaultdict(dict) + return self.helper(0, nums, k, cache, cnt) + + +if __name__ == "__main__": + obj = Solution() + print(obj.splitArray(nums=[7, 2, 5, 10, 8], k=2)) + print(obj.splitArray(nums=[1, 2, 3, 4, 5], k=2)) |