410. Split Array Largest Sum

題目敘述

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

Constraints:

• 1 <= nums.length <= 1000
• 0 <= nums[i] <= 10**6
• 1 <= m <= min(50, nums.length)

題目翻譯

今天有一個非負數的整數陣列 nums，然後一個非負數整數 m。今天需要把 nums 拆成 m 個陣列，然後試著找出在這拆解的各種組合之中，其子陣列總和是最小的。

解法解析

這題真的是難呢，但是解法卻讓這題一下變得簡單許多，是使用了 Binary Search。其概念是，我們今天不拆分 nums 而是來猜總和，這邊先定義為 X。其 X 的範圍必定是在 nums 中元素的最大值和其全部元素的總和中：nums.max() <= X <= nums.sum()。所以這題就會變得是我們在這個範圍中找出符合其條件的值，就會是 X。

一下子讓題目變簡單了，真的是很優雅的解法呀

解法範例

Go

func splitArray(nums []int, m int) int {
    var minLargestSplitSum int
    var left int
    var right int

    for _, num := range nums {
        if num > left {
            left = num
        }
        right += num
    }

    for left <= right {
        maxSumAllowed := (left + right) / 2
        if minSubarraysRequired(nums, maxSumAllowed) <= m {
            right = maxSumAllowed - 1
            minLargestSplitSum = maxSumAllowed
        } else {
            left = maxSumAllowed + 1
        }
    }

    return minLargestSplitSum
}

func minSubarraysRequired(nums []int, maxSumAllowed int) int {
    currentSum := 0
    splitsRequired := 0

    for _, element := range nums {
        if currentSum+element <= maxSumAllowed {
            currentSum += element
        } else {
            currentSum = element
            splitsRequired++
        }
    }

    splitsRequired++
    return splitsRequired
}

JavaScript

/**
 * @param {number[]} nums
 * @param {number} m
 * @return {number}
 */
var splitArray = function (nums, m) {
    const minSubarraysRequired = (maxSumAllowed) => {
        let currentSum = 0,
            splitsRequired = 0;
        for (const element of nums) {
            if (currentSum + element <= maxSumAllowed) {
                currentSum += element;
            } else {
                currentSum = element;
                splitsRequired++;
            }
        }
        return splitsRequired + 1;
    };

    let minimumLargestSplitSum = 0,
        left = Math.max(...nums),
        right = nums.reduce((a, b) => a + b, 0);
    while (left <= right) {
        const maxSumAllowed = Math.floor((left + right) / 2);

        if (minSubarraysRequired(maxSumAllowed) <= m) {
            right = maxSumAllowed - 1;
            minimumLargestSplitSum = maxSumAllowed;
        } else {
            left = maxSumAllowed + 1;
        }
    }

    return minimumLargestSplitSum;
};

Kotlin

class Solution {
    fun splitArray(nums: IntArray, m: Int): Int {
        var left = 0L
        var right = 0L
        for (num in nums) {
            left = maxOf(left, num.toLong())
            right += num
        }
        var minLargeestSplitSum = 0L

        while (left <= right) {
            val maxSumAllowed = left + (right - left) / 2
            if (minSubArraysRequired(nums, maxSumAllowed) <= m) {
                right = maxSumAllowed - 1
                minLargeestSplitSum = maxSumAllowed
            } else {
                left = maxSumAllowed + 1
            }
        }

        return minLargeestSplitSum.toInt()
    }

    private fun minSubArraysRequired(nums: IntArray, maxSumAllowed: Long): Int {
        var currentSum = 0
        var splitsRequired = 1

        for (num in nums) {
            if (currentSum + num <= maxSumAllowed) {
                currentSum += num
            } else {
                splitsRequired++
                currentSum = num
            }
        }
        return splitsRequired
    }
}

PHP

Python

class Solution:
    def splitArray(self, nums: List[int], m: int) -> int:

        def min_subarrays_required(max_sum_allowed: int) -> int:
            current_sum = 0
            splits_required = 0

            for element in nums:
                # Add element only if the sum doesn't exceed max_sum_allowed
                if current_sum + element <= max_sum_allowed:
                    current_sum += element
                else:
                    # If the element addition makes sum more than max_sum_allowed
                    # Increment the splits required and reset sum
                    current_sum = element
                    splits_required += 1

            # Return the number of subarrays, which is the number of splits + 1
            return splits_required + 1

        # Define the left and right boundary of binary search
        left, right = max(nums), sum(nums)
        while left <= right:
            # Find the mid value
            max_sum_allowed = (left + right) // 2

            # Find the minimum splits. If splits_required is less than
            # or equal to m move towards left i.e., smaller values
            if min_subarrays_required(max_sum_allowed) <= m:
                right = max_sum_allowed - 1
                minimum_largest_split_sum = max_sum_allowed
            else:
                # Move towards right if splits_required is more than m
                left = max_sum_allowed + 1

        return minimum_largest_split_sum

Rust

Swift

class Solution {
    func splitArray(_ nums: [Int], _ m: Int) -> Int {
        var minLargetSplitSum = 0
        var left = nums.max()!
        var right = nums.reduce(0, +)
        while left <= right {
            let maxSumAllowed = (left + right) / 2

            if minSubarraysRequired(nums, maxSumAllowed) <= m{
                right = maxSumAllowed - 1
                minLargetSplitSum = maxSumAllowed
            } else {
                left = maxSumAllowed + 1
            }
        }

        return minLargetSplitSum
    }

    func minSubarraysRequired(_ nums: [Int], _ max_sum_allowed: Int) -> Int {
        var currentSum = 0
        var splitsRequired = 0

        for num in nums {
            if currentSum + num <= max_sum_allowed {
                currentSum += num
            } else {
                currentSum = num
                splitsRequired += 1
            }
        }

        return splitsRequired + 1
    }
}