forked from kamyu104/LeetCode-Solutions
-
Notifications
You must be signed in to change notification settings - Fork 0
/
split-array-largest-sum.py
92 lines (82 loc) · 2.35 KB
/
split-array-largest-sum.py
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
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
# Time: O(nlogs), s is the sum of nums
# Space: O(1)
# Minimize the largest subarray sum.
class Solution(object):
def splitArray(self, nums, m):
"""
:type nums: List[int]
:type m: int
:rtype: int
"""
def canSplit(nums, m, s):
cnt, curr_sum = 1, 0
for num in nums:
curr_sum += num
if curr_sum > s:
curr_sum = num
cnt += 1
return cnt <= m
left, right = max(nums), sum(nums)
while left <= right:
mid = left + (right - left) / 2
if canSplit(nums, m, mid):
right = mid - 1
else:
left = mid + 1
return left
# Time: O(nlogs), s is the sum of nums
# Space: O(1)
# Maximize the smallest subarray sum.
class SolutionFindMaxMin(object):
def splitArray(self, nums, m):
"""
:type nums: List[int]
:type m: int
:rtype: int
"""
def canSplit(nums, m, s):
cnt, curr_sum = 1, 0
for num in nums:
curr_sum += num
if curr_sum > s:
curr_sum = 0
cnt += 1
return cnt <= m
left, right = min(nums), sum(nums)
while left <= right:
mid = left + (right - left) / 2
x = canSplit(nums, m, mid)
if x:
right = mid - 1
else:
left = mid + 1
return left
# Time: O(nlogs), s is the sum of nums
# Space: O(1)
# Maximize the smallest subarray sum.
class SolutionFindMaxMin2(object):
def splitArray(self, nums, m):
"""
:type nums: List[int]
:type m: int
:rtype: int
"""
def canSplit(nums, m, s):
cnt, curr_sum = 0, 0
for num in nums:
curr_sum += num
if curr_sum >= s:
curr_sum = 0
cnt += 1
return cnt < m
left, right = min(nums), sum(nums)
for i in xrange(left, right+1):
canSplit(nums, m, i)
while left <= right:
mid = left + (right - left) / 2
x = canSplit(nums, m, mid)
if x:
right = mid - 1
else:
left = mid + 1
return left - 1