FilesExpand file tree

 master

/

split-array-largest-sum.py

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

52 lines (48 loc) · 1.32 KB

 master

/

split-array-largest-sum.py

Copy path

Top

File metadata and controls

• Code
• Blame

52 lines (48 loc) · 1.32 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

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

# Time: O(nlogs), s is the sum of nums

# Space: O(1)

# Given an array which consists of non-negative integers and an integer m,

# you can split the array into m non-empty continuous subarrays.

# Write an algorithm to minimize the largest sum among these m subarrays.

#

# Note:

# Given m satisfies the following constraint: 1 <= m <= length(nums) <= 14,000.

#

# 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.

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 = 0, 0

for num in nums:

left = max(left, num)

right += num

while left <= right:

mid = left + (right - left) / 2;

if canSplit(nums, m, mid):

right = mid - 1

else:

left = mid + 1

return left