Участник:ArtemTovkes/split-array-largest-sum

Материал из DISCOPAL
< Участник:ArtemTovkes
Версия от 19:42, 3 декабря 2020; ArtemTovkes (обсуждение | вклад) (Новая страница: «Python3 https://leetcode.com/problems/split-array-largest-sum/ <code-python> class Solution(object): def __init__(self): pass def splitArray(se…»)

(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)
Перейти к: навигация, поиск

Python3

https://leetcode.com/problems/split-array-largest-sum/

class Solution(object):
 
    def __init__(self):
        pass
    def splitArray(self, nums, m):
        """
        :type nums: List[int]
        :type m: int
        :rtype: int
        """
        min_res = max(nums)
        max_res = sum(nums)
        low, high = min_res, max_res
        while low + 1 < high:
            mid = low + (high - low)//2
            if self.is_valid(nums, m, mid):
                high = mid
            else:
                low = mid
        if self.is_valid(nums, m, low):
            return low
        return high
 
    def is_valid(self, nums, m, n):
        count, current = 1, 0
        for i in range(len(nums)):
            if nums[i] > n:
                return False
            current += nums[i]
            if current > n:
                current = nums[i]
                count += 1
        if count > m:
            return False
        return True