给定一个非负整数数组和一个整数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，在所有情况中最小。

    方法1：动态规划

    分析：该问题中涉及到两个参数m, n；所以最大的状态空间数应该为m*n;
    这里定义dp[i][j]: 表示将数组的前i个数分割为j段所能表达的最大连续子数组和的最小值；
    状态转移: 考虑第j段的具体范围，枚举k, 使得前k个数被分割为j-1段，第k+1到第i个数为第j段。
    此时，第j段的子数组和的最大值等于max(dp[k][j-1], sum(k+1, i))。sum(t1, t2)表示数组下标[t1, t2]内的数和。
    结果：要使得子数组中和的最大值最小，可以列出如下的状态转移方程：
    dpi][j] = min{max(dp[k][j-1], sum(k+1, i))} (for k = 0 to i-1)
    对于状态f[i][j], 不能分出空的子数组，合法的状态有i >= j;对于不合法状态(i此时，还需要将f[0][0]的值初始化为0。当j=1的时候，唯一的可能性就是前k个数被分成一段。

    1. int splitArray(vector<int> &nums, int m){
    2.     int n = nums.size();
    3.     typedef long long LL;
    4.     vector<vector<LL>> dp(n+1, vector<LL>(m+1, LLONG_MAX));
    5.     vector<LL> prefixSum(n+1, 0);// prefix_sum used for calc sum(i, j) by prefixSum[j] - prefixSum[i]
    6.     for(int i=0; i<n; ++i)
    7.         prefixSum[i+1] = prefixSum[i] + nums[i];
    9.     dp[0][0] = 0;
    10.     for(int i=1; i<=n; ++i){
    11.         for(int j=1; j<=m; ++j){
    12.             for(int k=0; k<i; ++k){
    13.                 dp[i][j] = min(dp[i][j], max(dp[k][j-1], prefixSum[i] - prefixSum[k]));
    14.             }
    15.         }
    16.     }
    17.     return (int)dp[n][m]
    18. }

    方法2：二分查找(变形)和贪婪算法
    解题思路：根据题目的描述可以知道，子数组的最大值是有范围的，在区间[max(nums), sum(nums)]之间。
    假设：low = max(nums), high = sum(nums), mid = (low + high) / 2；此时可以计算数组和最大值不大于mid对应子数组个数cnt。
    如果：cnt > m, 说明划分的子数组多了，也就是mid设置的偏小；low = mid + 1;
    如果： cnt < m; 说明划分的子数组少了，即mid设置的偏大(或则正好是目标值)， 更新high = mid;

    int splitArray(vector<int>& nums, int m)
{
    typedef long long LL;
    LL low = nums[0], high = 0;
    for(auto i : nums){
        high += i;
        low = low >= i ? low : i;
    }
    while(low < high){
        LL mid = (low + high) >> 1;
        LL temp = 0;
        int cnt = 1; // 初始值必须为1
        for(auto i : nums){
            temp += i;
            if (temp > mid){
                temp = i;
                ++cnt;
            }
        }
        if (cnt > m)
            low = mid + 1;
        else
            high = mid;
    }
    return low;
}

    欢迎交流，批评指正！