Description

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，你需要将这个数组分成 m 个非空的连续子数组。设计一个算法使得这 m 个子数组各自和的最大值最小。

注意:
数组长度 n 满足以下条件:

1 ≤ n ≤ 1000
1 ≤ m ≤ min(50, n)
示例:

输入:
nums = [7,2,5,10,8]
m = 2

输出:
18

解释:
一共有四种方法将 nums 分割为 2 个子数组。
其中最好的方式是将其分为 [7,2,5] 和 [10,8]，
因为此时这两个子数组各自的和的最大值为 18，在所有情况中最小。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/probl…
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

• 这道题可以使用动态规划和二分搜索来做，使用动态规划的 Python 代码会超时，因此下面使用二分搜索。
• 对于题意，当 k 等于 nums 的元素个数时，此时的最小值就是数组的最大值；当 k = 1 时，此时的最小值就是整个数组的和。
• 因此，我们要求的结果一定在上面这两个值之间。
• 我们给定一个值 middle，然后我们对数组分组，使得每个组中的元素尽量多，并且其和小于等于 middle，统计总共分的的总组数 group；
• 如果 group 大于 k，说明 middle 这个值给小了，需要给一个更大的值，使得每组中容纳更多的数，使得总组数减小；
• 如果 group 小于 k，说明 middle 这个值给大了，需要给一个更小的值，使得没组中容纳更少的数，使得总组数增多；
• 如果 group 等于 k，说明此时把数组分成 k 组，每组的和都不大于 middle，此时我们尝试把 middle 减少 1，当用 middle 去划分数组有 k 组，middle -1 去划分数组大于 k 组时，middle 就是要求的结果。

# -*- coding: utf-8 -*-
# @Author:             何睿
# @Create Date:        2019-10-04 11:17:10
# @Last Modified by:   何睿
# @Last Modified time: 2019-10-05 16:13:51

from typing import List
from bisect import bisect_right


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

        prefix_sum = self.sum_cumulative(nums)
        left, right, count = max(nums), prefix_sum[-1], len(nums)

        while left < right:
            middle = left + ((right - left) >> 1)
            if self.is_greater(prefix_sum, middle, m, count):
                left = middle + 1
            else:
                right = middle

        return right

    def sum_cumulative(self, nums):
        prefix_sum = [nums[0]]
        for i in range(1, len(nums)):
            prefix_sum.append(prefix_sum[i - 1] + nums[i])

        return prefix_sum

    def is_greater(self, prefix_sum, max_num, m, count):

        pivot, start, group = max_num, 0, 0
        while start < count:
            start = bisect_right(prefix_sum, pivot, start)
            pivot = prefix_sum[start - 1] + max_num
            group += 1
            if group > m:
                return True

        return False

源代码文件在 这里。
©本文首发于 何睿的博客，欢迎转载，转载需保留 文章来源，作者信息和本声明.

题目要求

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.

将一个长度为 n 的正整数数组分割为 m 个非空的连续子数组，并分别计算每个子数组中所有元素的和。求一种分割方式，使得该分割方式生成的最大子数组和为所有分割方式中最小的。

比如题目中的例子 nums = [7,2,5,10,8]，m = 2
一共有四种分割方式：

1. [7], [2,5,10,8]
2. [7,2], [5,8,10]
3. [7,2,5], [8,10]
4. [7,2,5,8], [10]

其中第三种分割得到的最大子数组的和 是所有分割中最小的

思路一：动态规划

首先，我们可以通过递归的方式来遍历所有的分割方式，从而找到所有分割方式中最符合要求的那一种结果。代码如下：

    public int splitArray(int[] nums, int m) {// 计算 [0...i] 中所有元素的和
        int[] sums = new int[nums.length+1];
        for(int i = 1 ; i<=nums.length ; i++) {sums[i] = nums[i-1] + sums[i-1];
        }
        return splitArray(nums, m, 0, sums);
    }
    
    // 计算从 cur 位置开始，将其分割为 m 个子数组的最小分割场景
    public int splitArray(int[] nums, int m, int cur, int[] sums) {if(m == 1) {return sums[nums.length] - sums[cur];
        }
        int min = Integer.MAX_VALUE;
        int diff = Integer.MAX_VALUE;
        for(int i = cur+1 ; i<=nums.length-m+1 ; i++) {
            // 当前元素为止，左边的子数组的元素和
            int left = sums[i]-sums[cur];
            // 对右边的剩余元素递归的调用 splitArray 方法
            int right = splitArray(nums, m-1, i, sums);
            // 如果出现二者之间的差递增的情况，则说明距离最优分割越来越远，则停止继续尝试
            if(diff < Math.abs(left - right)) {break;}
            diff = Math.abs(left - right);
            min = Math.min(min, Math.max(left, right));
        }
        return min;
    }

这种方法在大数据量的场景下会出现超时的问题，本质在于我们没有足够的复用中间的所有场景，如对于 [i-j] 这个子数组的 k 次分割的最优结果。如果我们记录从 i 到数组结尾进行 k 次分割的最优结果，该结果记录为 dp[i][k]，则从 j 到数组结尾进行 k + 1 次分割的最优结果为min(max(num(j), dp[j+1][k]), max(nums(j)+num(j+1), dp[j+2][k])... )
代码如下：

    public int splitArray(int[] nums, int m)
    {
        int L = nums.length;
        // 记录 0 - i 的元素和
        int[] S = new int[L+1];
        S[0]=0;
        for(int i=0; i<L; i++)
            S[i+1] = S[i]+nums[i];

        // 如果 m =1，则最小分割结果对应的是整个数组中所有元素的和
        int[] dp = new int[L];
        for(int i=0; i<L; i++)
            dp[i] = S[L]-S[i];

        for(int s=1; s<m; s++)
        {for(int i=0; i<L-s; i++)
            {dp[i]=Integer.MAX_VALUE;
                for(int j=i+1; j<=L-s; j++)
                {int t = Math.max(dp[j], S[j]-S[i]);
                    if(t<=dp[i])
                        dp[i]=t;
                    else
                        break;
                }
            }
        }

        return dp[0];
    }

思路二：二分法

这是一个非常难想到的方法。二分法的难点一直在于如何划分初始边界，以及如何逐渐缩小边界并且确保左右指针可以相遇。在这里，边界被设置为该数组中可以得到的子数组元素和的最小值和最大值。
根据基本常识可知，数组的最大元素决定了该数组分割出的子数组的元素和的下界，而数组的元素和上界一定不会超过数组所有元素的和。
在确定了数组元素和的上界和下界之后，就需要找出一种方法，来不断压缩区间直到最后一种。

可以使用中间位置作为数组元素和的边界，即假设所有的连续数组的和都不会超过 mid 值。假如按照这种方式得到的分割结果大于了规定的 m 个，则说明 mid 值作为最大元素和上界并不能够做到只分割出 m 个子数组，因此最大元素和上界一定在 mid 和有界中间。同理，假如按照这种方式得到的分割结果小于等于规定的 m 个，则说明 mid 值作为最大元素和上界能够满足分割出 m 个子数组，但是可能还存在更优解。通过这种二分法思路得到的最后结果就是所需要的最小分割结果。

    public int splitArray2(int[] nums, int m) {
        long sum = 0;
        int max = Integer.MIN_VALUE;
        for(int i = 0 ; i<nums.length ; i++) {max = Math.max(max, nums[i]);
            sum += nums[i];
        }
        if(m == 1) {return (int)sum;
        }
        long lft = max;
        long rgt = sum;
        while(lft <= rgt) {long mid = (lft + rgt) / 2;
            if(valid(nums, m, mid)) {rgt = mid - 1;}else {lft = mid + 1;}
        }
        return (int) lft;
        
    }
    
    public boolean valid(int[] nums, int m, long target) {
        int count = 1;
        long sum = 0;
        for(int i = 0 ; i<nums.length ; i++) {sum += nums[i];
            if(sum > target) {sum = nums[i];
                count++;
                if(count > m) {return false;}
            }
        }
        return true;
    }