最大化连续子串最小sum (LC 410 变种)

最大化连续子串最小sum (LC 410)

有一个数组，分成K部分，要求， min of subarray sum is maximized,   [1,2,4,3,3]  分成3部分，  你可以分成   1| 2,4|3,3  最小数组 是1,  但是你分成 1,2 |4|3,3 最小的数组sum就变成了3.  3是想要的答案。 这个我提出了DP和recursive, 面试官都不满意, 最后用的是二分查找.    比如说你给 一个数 N , 看这个数组能不能被分成K部分, 每个部分都大于N，  如果不能，就试试N/2。


看G家面经 发现这道 LC410 变种， 请大家帮看看我的解法是否正确

1. class Solution(object):
   
2.     def splitArray(self, nums, m):
   
3.         """
   
4.         :type nums: List[int]
   
5.         :type m: int
   
6.         :rtype: int
   
7.         """
   
8.         def canDivideToM(target, nums, m):
   
9.             '''
   
10.             if we can divide nums to more than m subarray with target as sum
    
11.             for each subarray, it means the target is too small, if we can't             mean target is too big
    
12.             '''
    
13.             count=1
    
14.             total=0
    
15.             
    
16.             for num in nums:
    
17.                 total+=num
    
18.                 if total>=target:
    
19.                     total=0
    
20.                     count+=1
    
21.                     
    
22.                     if count > m:
    
23.                         return True
    
24.             return False
    
25.                         
    
26.         
    
27.         #low bound
    
28.         left= minNum = min(nums)
    
29.         #high bound
    
30.         right = sumNums = sum(nums)
    
31.         
    
32.         # Binary search Template
    
33.         while left<=right:
    
34.             mid = (left+right)/2
    
35.             
    
36.             if canDivideToM(mid, nums, m):
    
37.                 left=mid+1
    
38.             else:
    
39.                 right=mid-1
    
40.         return right
    
41.                
    
42.         
    
43.         

复制代码

小优化
1. high bond = sum/k instead of sum
2. 累加target的时候如果发现剩余的数<还需要的分段数，可以提前结束。

这就是巧克力甜度吧