410. Split Array Largest Sum
有两种解法：
- 按值二分: 左边界是array里的最大值，右边界是array的sum。按照贪心来做，a. 把array 从左边切割，b.尽量使得两刀之间的值靠近mid，但是小于mid，c. 最后会出现两种情况，一是可以把array切成超过m个subarray，说明mid太小了，否则说明mid太大了。
- DP：dp[s][j] 表示把 n[j]...n[L-1] 分成s份能获得的最小和，dp[s+1][i] = min{ max(dp[s][j], n[i]+...+n[j-1]) }, i+1 <= j <= L-s 从i到最后能分成s+1份的最小值就等于，j到最后能分成s份的最小值 和 i到j-1的和这两个值中比较大的值，再取最小，类似minmax，DP的写法可以用memory search感觉写起来要清爽一些。
DP的解法
class Solution(object):
def splitArray(self, nums, m):
"""
:type nums: List[int]
:type m: int
:rtype: int
"""
sums = [0]*len(nums)
sums[len(nums)-1] = nums[len(nums)-1] # sums 表示从某个index到最后一个点的subarray和
for i in range(len(nums)-2, -1, -1):
sums[i] = sums[i+1] + nums[i]
memo = [[0]*(m+1) for _ in range(len(nums))]
return self.search(nums, 0, m, sums, memo)
def search(self, nums, start, m, sums, memo):
if m == 1: # 如果只分成一个部分，从start到最后
return sums[start]
if memo[start][m] > 0:
return memo[start][m]
min_val = sys.maxint
total = 0
for i in range(start, len(nums)-m+1):
total += nums[i]
# total是从start到i这一段的和，这个与i+1到最后分成m-1份的最小值相比较，取其中的较大的值
# 然后loop i，取这些值中比较小的值。
min_val = min(max(total, self.search(nums, i + 1, m - 1, sums, memo)), min_val)
memo[start][m] = min_val
return min_val
二分法解法
class Solution(object):
def splitArray(self, nums, m):
"""
:type nums: List[int]
:type m: int
:rtype: int
"""
max_value = max(nums)
sum_value = sum(nums)
if m == 1:
return sum_value
# binary search
l = max_value
r = sum_value
while l + 1 < r:
mid = (l + r)/ 2
if self.valid(mid, nums, m):
r = mid
else:
l = mid
if self.valid(l, nums, m):
return l
else:
return r
def valid(self, target, nums, m):
count = 1;
total = 0;
for num in nums:
total += num
if total > target:
total = num
count += 1
if count > m:
return False
return True
