题目

题意分析

虽然题干只有短短一行半，但是说实话第一遍还真没看懂题目是什么意思，看了下边的例子才算是了解了要求什么。对于数组[7, 2, 5, 10, 8]，需要将其分割为2个连续子数组，示例中给了一种最好的分割方式，我们可以举一个不同的分割方式方便理解：[7]和[2, 5, 10, 8]这样分割出来的两个连续子数组，他们的和分别为7,25，所以最大值为25，表示的就是题干中所说的各自和的最大值；示例中最好的答案为18，也就是在所有的分割方案中，最小值为18，这个数就是我们要求解的值，通过示例还是比较容易理解的。

DP解法

刚开始看到题是没有什么思路的，但是，想起以前做过类似的分割数组的问题，于是想到了使用动态规划来解决，既然用DP，当然还是经典步骤走起来。

定义dp数组

这道题的dp数组定义还算相对容易，总共就一个包含n个元素的数组，将其分割为m个连续子数组，这样的话，分割为m个连续子数组的子问题必然是分割为k(1 <= k <= m)个连续子数组 ，所以用dp数组的一维表示分割的子数组的个数就很容易想到了，但是只有一维是不够的，因为dp[1]表示将数组分为一个子数组 ，dp[2]表示将数组分为两个连续子数组，这两个值之前是没有明显的关系，并不能使用已知解推出未知解，所以就要用到另一个n，作为数组的另一维。
那么dp数组也就定义出来了：dp[i][j] 表示前i个元素，分割为j个连续子数组，使得这 j 个子数组各自和的最大值最小，可能有点繁琐，就是按照题目的意思给出的定义。这里要注意的是只有i >= j的dp数组元素是有意义的，因为5个元素不可能分割为6个子数组的嘛。

状态转移方程

根据dp[i][j]的定义，可以想到，将数组分割为j个连续子数组可以拆分为：将数组的部分元素分割为j - 1个连续子数组，并将剩余元素作为另一个连续子数组，这样由于具体选择多少个元素作为前j - 1个子数组并不固定，所以要用一个变量来遍历每一种可能，可以得到如下的状态转移：

    dp[i][j] = Integer.MAX_VALUE;
    for (int k = j - 1; k < i; k++) {
        dp[i][j] = Math.min(dp[i][j], Math.max(dp[k][j - 1], sum[i] - sum[k]));
    }

这里通过max部分求得连续子数组各自和的最大值，在通过min部分，求出所有可能的分割方法中，该值的最小值即为需要求解的dp[i][j]，不过要注意初始化dp[i][j]的值足够大，保证第一次计算时可以有的比。另外，就像定义部分说的，5个元素不可能分割为6个子数组，所以可以让k从j - 1开始遍历。

初始化状态

由于dp数组的最终状态即是将n个元素，分割为m个连续子数组，使得这 m 个子数组各自和的最大值最小。那么最初始的状态就是n = 0 和 m = 0所对应的两行(列)元素，但是单纯从定义找初始值并不好找：将0个元素分割为若干个连续子数组与将若干个元素分割为0个连续子数组都没有合适的值来代表，所以我们看状态转移方程，这两行(列)元素只在计算各自和的最大值时被用到，而n = 0这一行只有dp[0][0] = 0有意义，其他元素均不会被遍历到，所以只需考虑m = 0这一列，假设要求的为dp[3][1]，那么他要用到的就是dp[3][0]，可是这个元素毫无意义，而且不应该取它，所以可以令它为Integer.MAX_VALUE，这样只会保留遍历dp[0][0]时，有意义的sum[i] - sum[k]，其他情况均不保留。

完整代码

public int splitArray(int[] nums, int m) {
        int n = nums.length;
        int[][] dp = new int[n + 1][m + 1];
        // 求前缀和
        int[] sum = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            sum[i] = sum[i - 1] + nums[i - 1];
        }
        for(int i = 1; i <= n; i++){
            dp[i][0] = Integer.MAX_VALUE;
        }

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= Math.min(m, i); j++) {
                dp[i][j] = Integer.MAX_VALUE;
                for (int k = j - 1; k < i; k++) {
                    dp[i][j] = Math.min(dp[i][j], Math.max(dp[k][j - 1], sum[i] - sum[k]));
                }
            }
        }
        return dp[n][m];
    }

其实初始化部分就相当于只把dp[0][0]赋值为0，其余全部初始化为Integer.MAX_VALUE，可以将其从循环中拿出来在最开始的位置初始化，都是一样的。

二分法

做这道题我只想到了动态规划的方法，二分法还真的是没有什么思路，不过看了眼题解豁然开朗。二分法的主要思想就是遍历可能的结果，然后验证其正确性，最终锁定一个正确的元素就是正确答案了。首先就是高低取值的范围，很显然最大值就是整个数组划分为一个子数组所得到的值，也就是数组所有元素的和；而最小值也就是将数组的n个元素划分为n个子数组，求的其中的最大值，也就是所有元素中最大元素的值。
范围有了，还需要的就是怎样迭代，核心思想是验证，那么验证数值mid通过的情况(也就是数组可以划分为m个连续子数组，且保证子数组的和均小于mid)，这时比mid大的数肯定可以通过验证，而比mid的小的就不一定，所以要更新右边界；反之更新左边界。
还需要考虑的就是验证方法，如果直接考虑分割m个子数组的可能性还是很多的，但是如果反过来考虑保证子数组的和小于mid，求分割的子数组的个数，这样验证就会简单许多，只要求出来的子数组的个数不超过m就可以通过验证。因为分割4次就可以满足子数组和小于k了，多分割几次也是肯定满足条件的。

完整代码

class Solution {
    public int splitArray(int[] nums, int m) {
        int n = nums.length;
        // 求前缀和
        int sum = 0;
        int maxNum = 0;
        for (int i = 1; i <= n; i++) {
            sum += nums[i - 1];
            maxNum = Math.max(maxNum, nums[i - 1]);
        }

        int l = maxNum, r = sum;
        while (l < r) {
            int mid = l + (r - l) / 2;
            if (check(nums, mid, m)) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }
        return l;
    }

    /**
     * 检查数组是否能划分为和不超过k的m个连续子数组
     * 
     * @param nums
     * @param k
     * @param m
     * @return
     */
    public boolean check(int[] nums, int k, int m) {
        int count = 1;
        int tempSum = 0;
        for (int i = 0; i < nums.length; i++) {
            if (tempSum + nums[i] > k) {
                tempSum = nums[i];
                count++;
            } else {
                tempSum += nums[i];
            }
        }
        return count <= m;
    }
}

二分法其实要简单许多，主要是验证通过的check函数，二分部分就是套一个格式即可。不过二分法的效率确实要高很多，通常在求(使...的最大值尽可能小)就可以考虑使用二分法，真的学习到了一些套路。
如果文章有写的不对的地方还请指出。
感恩相遇~