410.split-array-largest-sum.md

問題

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

回答

初回の回答:

配列 nums を k 分割するとき、新たにできた各配列の合計の最大値が最小になるように分割する。この最小値を求めよ、という問題。

n 個の nums を k 分割するときの組み合わせは ${n-1}C{k-1}$ である。

_{※ n 個の要素の間 n-1 箇所のうち k-1 枚の敷居を立てると考える。}

ただ、以下の条件を考えると、数字が十分大きい場合、膨大なパターンの組み合わせができてしまうため、すべての組み合わせのうちから最小値を求めるのは燃費が悪い。

• 1 <= nums.length <= 1000
• 1 <= k <= min(50, nums.length)

ここまでは理解できたが、実際にどのようにすれば計算量を少なくできるかが分からずギブアップしたので、 公式の回答を参考にした。 https://leetcode.com/problems/split-array-largest-sum/solutions/1668183/split-array-largest-sum/

各配列の合計の取りうる範囲から二分探索で絞っていく。たとえば、合計の最大値が X 以下になるには何分割すればいいかを考える。k 分割以下に収まるなら、X はもっと小さくして OK 。k 分割に収まらないなら、X はもっと大きくして OK。こうしてちょうど k 分割したときの X の最小値（それ以上小さくしたら k+1 分割しなきゃいけなくなる）が導き出せる。

impl Solution {
    pub fn split_array(nums: Vec<i32>, k: i32) -> i32 {
        let mut l = *nums.iter().max().unwrap();
        let mut r = nums.iter().sum();
        while l < r {
            let m = l + (r - l) / 2;
            let min_subarray_required = {
                let mut split_required = 0;
                let mut current_sum = 0;
                for i in &nums {
                    if current_sum + i <= m {
                        current_sum += i;
                    } else {
                        current_sum = *i;
                        split_required += 1;
                    }
                }
                split_required + 1
            };
            if min_subarray_required <= k {
                r = m;
            } else {
                l = m + 1;
            }
        }
        l
    }
}