aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--split_array_largest_sum.c39
-rw-r--r--split_array_largest_sum.py48
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))