Given an array which consists of non-negative integers and an integerm, you can split the array intomnon-empty continuous subarrays. Write an algorithm to minimize the largest sum among thesemsubarrays.

Note:
Ifnis the length of array, assume the following constraints are satisfied:

• 1 ≤ n ≤ 1000
• 1 ≤ m ≤ min(50, n)

Examples:

``````Input:

nums = [7,2,5,10,8]

m = 2

Output:18

Explanation:
There are four ways to split nums into two subarrays.
The best way is to split it into [7,2,5] and [10,8],
where the largest sum among the two subarrays is only 18.
``````

Thoughts:

1. Binary search to query the minimum value of partition until converge. As per each partition size, there is a number of partition calculated. (Original post)
2. DP: dp[i][j] = min{max{dp[k][j-1], subsum(k + 1, i)}}, 0 <= k < i (Original post)
3. DP: 1D state array with appropriate initialization direction: r from 2 to m, k is shared for the same r (cuts), decreasing from n-1 to r, i (subarray boundary) is decreasing frm n to r

Code: Binary search through ranges of values. T: O(nlogn)

``````class Solution {
public:
int splitArray(vector<int>& nums, int m) {
int max_val = 0; long sum = 0;
for (int num : nums){
max_val = max(max_val, num);
sum += num;
}
// if (m == 1) return (int)sum;
long l = max_val , r = sum;
while(l <= r){
int mid = l + (r - l >> 1);
if(valid_partition(mid, nums, m)){
r = mid - 1;
}
else l = mid + 1;
}

return (int)l;
}

bool valid_partition(int target, vector<int>& nums, int m){
int count = 1; long total = 0;
for (int num: nums){
total += num;
if (total > target){
count ++;
total = num;
if (count > m) return false;
}
}

return true;
}
};
``````

Code: DP T: O(n^2m)

``````class Solution(object):
def splitArray(self, nums, m):
"""
:type nums: List[int]
:type m: int
:rtype: int
"""
n = len(nums)
if not n:
return 0
pre_sum =  * (n + 1)
for i in range(n):
pre_sum[i + 1] = pre_sum[i] + nums[i]

sub_sum = lambda i, j: pre_sum[j + 1] - pre_sum[i]
sub_cand = lambda k, j, i: max(dp[k][j], sub_sum(k + 1, i))

# dp = [ * m for _ in range(n)]
dp = [[0 for _ in range(m + 1)] for _ in range(n)]

for i in range(n):
dp[i] = pre_sum[i + 1]
k = 0
for j in range(2, m + 1): # assume j <= i + 1
# while k + 1 < i and max(dp[k][j - 1], sub_sum(k+1, i)) > max(dp[k + 1][j - 1], sub_sum(k + 2, i)):
min_val = pre_sum[-1]
for k in range(i + 1):
min_val = min(min_val, sub_cand(k, j - 1, i))
dp[i][j] = min_val

return dp[n - 1][m]
``````

Code: DP T: O(nm), S: O(n)

``````class Solution(object):
def splitArray(self, nums, m):
'''
O(n) space
'''
n = len(nums)
sums = 
for v in nums:
sums+= [sums[-1]+v]
dp = list(sums)

dp_cal = lambda j: max(dp[j], sums[i]-sums[j])

for r in range(2, m + 1):
k = n - 1
for i in range(n, r - 1, -1):
while k >= r and dp_cal(k-1) <= dp_cal(k):
k -= 1
dp[i] = dp_cal(k)

return dp[n]
``````
``````# """
# This is Master's API interface.
# You should not implement it, or speculate about its implementation
# """
#class Master(object):
#    def guess(self, word):
#        """
#        :type word: str
#        :rtype int
#        """

class Solution(object):
def findSecretWord(self, wordlist, master):
"""
:type wordlist: List[Str]
:type master: Master
:rtype: None
"""
match = lambda w1, w2: sum(i == j for i, j in zip(w1, w2))

n = 0
while n < 6:
count = collections.Counter(w1 for w1, w2 in itertools.permutations(wordlist, 2) if match(w1, w2) == 0)
guess = min(wordlist, key = lambda w: count[w])
n = master.guess(guess)
wordlist = [w for w in wordlist if match(w, guess) == n]
``````