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
40
41
42
43
44
45
46
47
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))
|