题目描述补充

数组划分

给定一个整数数组 nums 和一个整数 k，要求将数组 nums 划分为 k 个连续的子数组（每个子数组至少包含一个元素），使得这些子数组的最大和尽可能小。请返回这个最小的最大子数组和。

示例 1:

输入: nums = [1, 2, 1, 2, 6, 7, 5, 1], k = 4
输出: 4
解释: 数组可以被划分为 [1, 2, 1], [2, 6], [7], [5, 1]，每个子数组的和分别为 4, 8, 7, 6。
这些子数组的最大和是 8，但我们可以划分得更均匀些，得到 [1, 2], [1, 2], [6, 7], [5, 1]，
此时最大和为 7。但是我们可以继续划分得到 [1], [2], [1], [2], [6], [7], [5], [1]，
此时最大和为 6，但这不是最小的最大子数组和，因为我们可以得到 [1, 2, 1], [2, 6], [7], [5, 1]，
此时最大和为 4，为所求。

示例 2:

输入: nums = [1, 2, 1, 4, 3, 5, 2, 6], k = 3
输出: 6
解释: 数组可以划分为 [1, 2, 1], [4, 3], [5, 2, 6]，每个子数组的和分别为 4, 7, 13。
最大和为 13，但我们可以通过更均匀的划分得到 [1, 2], [1, 4], [3, 5, 2], [6]，
此时最大和为 6，为所求。

PHP 示例代码

function splitArray($nums, $k) {
    $n = count($nums);
    $prefixSum = array_fill(0, $n + 1, 0);
    for ($i = 0; $i < $n; $i++) {
        $prefixSum[$i + 1] = $prefixSum[$i] + $nums[$i];
    }

    $left = max($nums); // 最小可能的最大子数组和至少为数组中的最大元素
    $right = $prefixSum[$n]; // 最大可能的最大子数组和是整个数组的和

    while ($left < $right) {
        $mid = $left + floor(($right - $left) / 2);
        if (canPartition($prefixSum, $mid, $k)) {
            $right = $mid;
        } else {
            $left = $mid + 1;
        }
    }

    return $left;
}

function canPartition($prefixSum, $maxSum, $k) {
    $count = 1; // 已经分好的一组
    $currentSum = 0;
    for ($i = 1; $i < count($prefixSum); $i++) {
        if ($prefixSum[$i] - $currentSum > $maxSum) {
            $count++;
            $currentSum = $prefixSum[$i];
            if ($count > $k) {
                return false;
            }
        } else {
            $currentSum = $prefixSum[$i];
        }
    }
    return true;
}

// 测试
$nums = [1, 2, 1, 2, 6, 7, 5, 1];
$k = 4;
echo splitArray($nums, $k); // 输出 4

Python 示例代码

def splitArray(nums, k):
    n = len(nums)
    prefix_sum = [0] * (n + 1)
    for i in range(n):
        prefix_sum[i + 1] = prefix_sum[i] + nums[i]

    left = max(nums)
    right = prefix_sum[-1]

    while left < right:
        mid = (left + right) // 2
        if can_partition(prefix_sum, mid, k):
            right = mid
        else:
            left = mid + 1

    return left

def can_partition(prefix_sum, max_sum, k):
    count = 1
    current_sum = 0
    for i in range(1, len(prefix_sum)):
        if prefix_sum[i] - current_sum > max_sum:
            count += 1
            current_sum = prefix_sum[i]
            if count > k:
                return False
        else:
            current_sum = prefix_sum[i]
    return True

# 测试
nums = [1, 2, 1, 2, 6, 7, 5, 1]
k = 4
print(splitArray(nums, k))  # 输出 4

JavaScript 示例代码

function splitArray(nums, k) {
    const n = nums.length;
    const prefixSum = [0].concat(nums.reduce((acc, curr) => acc.concat(acc[acc.length - 1] + curr), [0]));

    let left = Math.max(...nums);
    let right = prefixSum[n];

    while (left < right) {
        const mid = Math.floor((left + right) / 2);
        if (canPartition(prefixSum, mid, k)) {
            right = mid;
        } else {
            left = mid + 1;
        }
    }

    return left;
}

function canPartition(prefixSum, maxSum, k) {
    let count = 1;
    let currentSum = 0;
    for (let i = 1; i <= prefixSum.length - 1; i++) {
        if (prefixSum[i] - currentSum > maxSum) {
            count++;
            currentSum = prefixSum[i];
            if (count > k) return false;
        } else {
            currentSum = prefixSum[i];
        }
    }
    return true;
}

// 测试
const nums = [1, 2, 1, 2, 6, 7, 5, 1];
const k = 4;
console.log(splitArray(nums, k)); // 输出 4

码小课网站中有更多相关内容分享给大家学习，涵盖各类算法和数据结构知识，帮助提升编程能力。