'''
Given an array nums 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.

Example 1:

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.
Example 2:

Input: nums = [1,2,3,4,5], m = 2
Output: 9
Example 3:

Input: nums = [1,4,4], m = 3
Output: 4

'''

class Solution:
    def splitArray(self, nums: List[int], m: int) -> int:
        weights = nums
        D = m
        low,hi=max(weights),sum(weights)

        while(low<hi):

            partitions,total=1,0
            mid=(low+hi)//2

            for w in weights:

                if(total+w>mid):
                    partitions=partitions+1
                    total=w  #we start calculating weight of next partition

                #else we keep updating weight of current partitiion
                else:
                    total=total+w

            if(partitions<=D):
                hi=mid
                print("High",hi)

            else:
                low=mid+1

        return low
