題目

題意分析

雖然題干只有短短一行半，但是說實(shí)話第一遍還真沒看懂題目是什么意思，看了下邊的例子才算是了解了要求什么。對于數(shù)組[7, 2, 5, 10, 8]，需要將其分割為2個(gè)連續(xù)子數(shù)組，示例中給了一種最好的分割方式，我們可以舉一個(gè)不同的分割方式方便理解：[7]和[2, 5, 10, 8]這樣分割出來的兩個(gè)連續(xù)子數(shù)組，他們的和分別為7,25，所以最大值為25，表示的就是題干中所說的各自和的最大值；示例中最好的答案為18，也就是在所有的分割方案中，最小值為18，這個(gè)數(shù)就是我們要求解的值，通過示例還是比較容易理解的。

DP解法

剛開始看到題是沒有什么思路的，但是，想起以前做過類似的分割數(shù)組的問題，于是想到了使用動態(tài)規(guī)劃來解決，既然用DP，當(dāng)然還是經(jīng)典步驟走起來。

定義dp數(shù)組

這道題的dp數(shù)組定義還算相對容易，總共就一個(gè)包含n個(gè)元素的數(shù)組，將其分割為m個(gè)連續(xù)子數(shù)組，這樣的話，分割為m個(gè)連續(xù)子數(shù)組的子問題必然是分割為k(1 <= k <= m)個(gè)連續(xù)子數(shù)組 ，所以用dp數(shù)組的一維表示分割的子數(shù)組的個(gè)數(shù)就很容易想到了，但是只有一維是不夠的，因?yàn)?code>dp[1]表示將數(shù)組分為一個(gè)子數(shù)組 ，dp[2]表示將數(shù)組分為兩個(gè)連續(xù)子數(shù)組，這兩個(gè)值之前是沒有明顯的關(guān)系，并不能使用已知解推出未知解，所以就要用到另一個(gè)n，作為數(shù)組的另一維。
那么dp數(shù)組也就定義出來了：dp[i][j] 表示前i個(gè)元素，分割為j個(gè)連續(xù)子數(shù)組，使得這 j 個(gè)子數(shù)組各自和的最大值最小，可能有點(diǎn)繁瑣，就是按照題目的意思給出的定義。這里要注意的是只有i >= j的dp數(shù)組元素是有意義的，因?yàn)?個(gè)元素不可能分割為6個(gè)子數(shù)組的嘛。

狀態(tài)轉(zhuǎn)移方程

根據(jù)dp[i][j]的定義，可以想到，將數(shù)組分割為j個(gè)連續(xù)子數(shù)組可以拆分為：將數(shù)組的部分元素分割為j - 1個(gè)連續(xù)子數(shù)組，并將剩余元素作為另一個(gè)連續(xù)子數(shù)組，這樣由于具體選擇多少個(gè)元素作為前j - 1個(gè)子數(shù)組并不固定，所以要用一個(gè)變量來遍歷每一種可能，可以得到如下的狀態(tài)轉(zhuǎn)移：

    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部分求得連續(xù)子數(shù)組各自和的最大值，在通過min部分，求出所有可能的分割方法中，該值的最小值即為需要求解的dp[i][j]，不過要注意初始化dp[i][j]的值足夠大，保證第一次計(jì)算時(shí)可以有的比。另外，就像定義部分說的，5個(gè)元素不可能分割為6個(gè)子數(shù)組，所以可以讓k從j - 1開始遍歷。

初始化狀態(tài)

由于dp數(shù)組的最終狀態(tài)即是將n個(gè)元素，分割為m個(gè)連續(xù)子數(shù)組，使得這 m 個(gè)子數(shù)組各自和的最大值最小。那么最初始的狀態(tài)就是n = 0 和 m = 0所對應(yīng)的兩行(列)元素，但是單純從定義找初始值并不好找：將0個(gè)元素分割為若干個(gè)連續(xù)子數(shù)組與將若干個(gè)元素分割為0個(gè)連續(xù)子數(shù)組都沒有合適的值來代表，所以我們看狀態(tài)轉(zhuǎn)移方程，這兩行(列)元素只在計(jì)算各自和的最大值時(shí)被用到，而n = 0這一行只有dp[0][0] = 0有意義，其他元素均不會被遍歷到，所以只需考慮m = 0這一列，假設(shè)要求的為dp[3][1]，那么他要用到的就是dp[3][0]，可是這個(gè)元素毫無意義，而且不應(yīng)該取它，所以可以令它為Integer.MAX_VALUE，這樣只會保留遍歷dp[0][0]時(shí)，有意義的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];
    }

其實(shí)初始化部分就相當(dāng)于只把dp[0][0]賦值為0，其余全部初始化為Integer.MAX_VALUE，可以將其從循環(huán)中拿出來在最開始的位置初始化，都是一樣的。

二分法

做這道題我只想到了動態(tài)規(guī)劃的方法，二分法還真的是沒有什么思路，不過看了眼題解豁然開朗。二分法的主要思想就是遍歷可能的結(jié)果，然后驗(yàn)證其正確性，最終鎖定一個(gè)正確的元素就是正確答案了。首先就是高低取值的范圍，很顯然最大值就是整個(gè)數(shù)組劃分為一個(gè)子數(shù)組所得到的值，也就是數(shù)組所有元素的和；而最小值也就是將數(shù)組的n個(gè)元素劃分為n個(gè)子數(shù)組，求的其中的最大值，也就是所有元素中最大元素的值。
范圍有了，還需要的就是怎樣迭代，核心思想是驗(yàn)證，那么驗(yàn)證數(shù)值mid通過的情況(也就是數(shù)組可以劃分為m個(gè)連續(xù)子數(shù)組，且保證子數(shù)組的和均小于mid)，這時(shí)比mid大的數(shù)肯定可以通過驗(yàn)證，而比mid的小的就不一定，所以要更新右邊界；反之更新左邊界。
還需要考慮的就是驗(yàn)證方法，如果直接考慮分割m個(gè)子數(shù)組的可能性還是很多的，但是如果反過來考慮保證子數(shù)組的和小于mid，求分割的子數(shù)組的個(gè)數(shù)，這樣驗(yàn)證就會簡單許多，只要求出來的子數(shù)組的個(gè)數(shù)不超過m就可以通過驗(yàn)證。因?yàn)榉指?次就可以滿足子數(shù)組和小于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;
    }

    /**
     * 檢查數(shù)組是否能劃分為和不超過k的m個(gè)連續(xù)子數(shù)組
     * 
     * @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;
    }
}

二分法其實(shí)要簡單許多，主要是驗(yàn)證通過的check函數(shù)，二分部分就是套一個(gè)格式即可。不過二分法的效率確實(shí)要高很多，通常在求(使...的最大值盡可能小)就可以考慮使用二分法，真的學(xué)習(xí)到了一些套路。
如果文章有寫的不對的地方還請指出。
感恩相遇~