Leetcode 410 Split Array Largest Sum [Hard] Python Binary Search

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: If n is the length of array, assume the following constraints are satisfied:

1 ≤ n ≤ 1000

1 ≤ m ≤ min(50, n)

 
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.

この問題は一見手がつけられない.問題は配列を分割して最小の可能性のある最大のサブ配列とを探すと言っているので、少し拗ねている.翻訳するとmサブ配列に分解して、連続しなければならなくて、それからこれらのサブ配列の中で最大の和、異なる分解法に従って、毎回最大のサブ配列と異なって、1種のアルゴリズムを見つけて最も大きいサブ配列の和の最小値を探し出すことができます
配列を分割するという考え方で行き詰まるので、難しすぎてDFSでも見つからないのですが、hard問題である以上、他の解法を考えてみましょう
直接答えを言って、binary search、どんなbinary search法ですか?
First,forget aboutが何組に分かれているかという質問ですが、単にグループ化して、勝手に何組に分けて、何個の数字が何組に分かれているのかというと、答えはこの数字の最大値で、最悪ですか?最悪は1組も分けず、直接和を取るのが答えです.はい、最良と最悪の場合、私たちはまず1つの値を確定します.例えば、最良と最悪の平均値を確定します.この平均値でsliding windowグループを作ります.あなたのグループがこの平均値より大きいたびに、新しいグループを開きます.すべてのグループを分けた後、どのくらいのグループに分ける必要があるかを見てみましょう.必要なグループが規定のグループより大きい場合は、では、この平均値が低くなったことを説明し、平均値を高くしてグループ数を減らし、規定で区別できるグループより少ないと、平均値が高くなったことを説明し、平均値を低くしてグループ数を増やすことができます.繰り返して、最終的にこの平均値を確定すればいいので、どのようにグループ化するかを知る必要はありません.
 
Code:

class Solution:
    def splitArray(self, nums: List[int], m: int) -> int:
        left=max(nums)
        right=sum(nums)
        
        while leftmid:
                    total=num
                    count+=1

            if count>m:
                left=mid+1
            else:
                right=mid
        return left