Problem statement

https://leetcode.com/problems/before-and-after-puzzle/

Solution

This problem I can say is dual to problem 0410. Split Array Largest Sum: there we need to minimize maximimum of sums in partition, here we need to maximize minimum of sums in partition. Again use function check(Q) which answer the question: if we take that in each part we need to have sum >= Q, is it possible to have at least K+1 parts.

Complexity

Time complexity is O(n*log(Q)), where Q = sum(nums)//(K+1) + 1.

Code

class Solution:
    def maximizeSweetness(self, nums, K):
        def check(Q):
            acc, ans = 0, 0
            for num in nums + [0]:
                if acc < Q:
                    acc += num
                else:
                    acc = num
                    ans += 1
            return ans >= K + 1

        beg, end = 1, sum(nums)//(K+1) + 1
        while beg + 1 < end:
            mid = (beg + end)//2
            if not check(mid):
                end = mid
            else:
                beg = mid
        
        return beg